I'm surprised no one has mentioned AWS dedicated instances: http://aws.amazon.com/dedicated-instances/

20% more expensive but it seems like the easiest way to fix the problem if you're already on Amazon.

That said, I totally agree that Cloud-based IaaS is not a good fit for every situation.