If you continuously use full CPU on a shared server, chances are your account will be removed at some point.

Have you read Vanitygen: Vanity bitcoin address generator/miner [v0.22] yet? You're going to want to use oclvanitygen, running on a GPU. My old laptop does 9 Mkeys/s on it's GPU, but I've seen claims of hundreds of Mkeys/s on modern GPUs.
It's probably going to be difficult to find a VPS with decent GPU.

There's also VanitySearch (Yet another address prefix finder), which is said to be faster, but I haven't tested it by myself yet.

TL;DR: you're going to want to use a GPU. Or, if you're looking for only one or a few specific address prefixes, you could use split key so someone with a decent GPU can generate it for you. If you do this right, it is completely secure, and hiring a few days GPU-time from someone might be cheaper than running vanitygen on CPU for months.