No shared hosting seems to imply that VPS won't cut it either--depends on what "shared hosting" really means. So you are left with looking for a dedicated hosting plan. I'd say check out a company like Rackspace (disclosure: I work there).
So really the question is: is there a company that'll manage the damn server(s) for us so that we get to deal with a nice, clean abstraction similar to shared hosting?
Basically I want a HIPAA-compliant Heroku (though in this case not for Ruby).
Give one large VPS to your production app, and create other VPSes for testing or development purposes.
The reason you want to use a VPS on top of your own dedicated hardware is to gain the benefits of VPS control, including easy archiving of the entire system, snapshots, easy moves to new hardware even if the hardware is different, etc.
I think that's the key.
My employer hopes that a virtual machine on a private VLAN, with a fully-encrypted virtual disk, qualifies. This seems reasonable to me, but reasonableness isn't necessarily a part of any regulation.
I can't find any links about this though and it's been months since I've kept up on OpenBSD-misc, so I might be full of shit.
Personally, I would tend to choose a theoretically-insecure VPS over a vhost environment any day.