Well-established privacy-hardcore hosting services look like an ideal match too:
http://cb3rob.net/
http://heihachi.net/

Both already provide anonymous payment means (Heihachi accepts Ukash, cb3rob might accept special arrangements).