First some terminology: Debian 5 is the distribution, and the 2.6.18.8 vs. 2.6.32 thing is the kernel
If you're running on a smaller VPS (e.g. anything smaller than 2 or 4GB of RAM or so), you'll probably want to use 32-bit instead of 64-bit if at all possible: all other things being equal, the 64-bit architecture wastes more RAM. This will require re-deploying from scratch, but it's something to consider.
As for the kernel choice, it depends on your application... 2.6.18.8 is a much older kernel, but uses a different way of handling Xen than newer kernels. A year or two ago, it was certainly more stable than the newer kernels under Xen, but the situation improved drastically over the past year. Some report it's faster, a few report it's slower, and many report it's the same. You'll have to try with your workload.
(Also note that some distributions, including Ubuntu 9.10, Slackware, and Arch, require the newer kernels. If you can boot under 2.6.18.8, then Debian 5 is not one of them.)