Which VPS providers are the most popular or notable for hosting bitcoind instances?
BitVPS offers a VPS with a pre-installed and synced bitcoind, and of course they accept payment in Bitcoin.  Email the owner (james@bitvps.com) for details.