Is it truly impossible to separate VMs running on the same HW?

More and more results appear, like this last one, on weaknesses and vulnerabilities of Virtual Machines running on usual (commodity) hardware. The most troublesome results are not due to software vulnerabilities, but rely only on the hardware architecture which supports it. If cryptographic private keys can be stolen and covert channels can be established evading the current isolation mechanisms provided by hardware and virtualization software (see also my previous posts on Clouds), how much can we trust at least the IaaS Cloud Services?