After a few hours working on the issue I was able to find the problem.
When you LIST packages in NuGet server you point to http://nugetserver.com/nuget. However when you are trying to PUSH or DELETE a package you need to point to http://nugetserver.com without the nuget folder in the path.
What happens is that NuGet.exe append /api/v2/package to the URL turning it into http://nugetserver.com/api/v2/package
I think this is far from optimal because it makes you add two different sources to your nuget.exe.config: one for the get/list and another for pushing/deleting packages.