If a PaaS can't beat the internal price (including time, hiring ops people,etc), they're fighting a losing battle.
Even worse, most internal measurements drastically underestimate the competence required.
I went VPS because:
1. I'm more familiar with configuring my own web apps then trying to use someone else's admin console. (Low opinion of said consoles that I've seen in the past, but haven't tried Heroku or other new services.)
2. I need to run Node.js, PHP, and Ruby all on the same server. (Actually, just PHP and Node.js, which are in the same web app and so need access to a shared database. Ruby could be elsewhere at the moment.)
I'm still on VPS because:
1. Already paying for it, hasn't been a year yet
2. I still don't understand the new PaaS thing
3. PHP + Node.js PaaS host? Preferably with name recognition on par with Heroku, but at least lots of good reviews.
Complications of VPS are numerous, so I won't enumerate them. Lots of things to configure, update, and keep alive. Also it isn't the same OS as my dev machine plus I have to manage security for a public server but not for my desktop machine.
EDIT: just thought of one more reason I use VPS, I actually like ssh shell access. Ability to edit files and run arbitrary commands, many innumerable uses of this.
When I was in their beta program when they first started out they also gave you shell access to the machine so you could see what was being deployed, and run arbitrary commands (perfect for having an Python app that required running paste for upgrading the DB to the latest version).
In my experience with them I had absolutely no issues, it was fast to configure and set up and their command line tools were fantastic. It used git if you wanted it to, or could use any arbitrary directory and upload the contents.
Not only that but you could modify the nginx config file to change redirects and set static directories that shouldn't be handled by WSGI so that you could take a load off the Python app from serving up requests for static content.
I haven't used dotCloud in over 8+ months now, if not longer, their pricing just didn't make sense for me, and I found it cheaper with all the sites I host to just go with a single dedicated server rather than use their services so maybe a lot has changed, but they sound like what you need.