Notable that the GPU seemed to run far faster than the CPU for these calculation instances. I think many of the low Hamming achievers used Nvidia GPUs using CUDA which ran up to 700 million hashes per second (seeing the tesla machine in the article).

So you probably want to go for GPU than CPU. There's a service called Hoopoe that does GPU cloud computing that uses CUDA: http://www.gass-ltd.co.il/hoopoe/

Amazon has "high-cpu" instances: http://aws.amazon.com/ec2/instance-types/