I've certainly seen virtualization environments where RAM is a much larger fraction of the physical server's cost than the CPUs. How much RAM are you using when you aren't using many CPU cycles?
Big consumers of memory tend to be caching layer, which could (should, actually) run on different machines and bill based on memory usage.
I have to admit scheduling CPU and memory is an issue, but that shouldn't be the excuse to adopt a model that discourage optimizing for CPU usage.