I dont think 9.04 has a new enough kernel, so you would have to use our Xen kernel instead rather than the distributions.
If you just have a single partition for / (and no others except swap), at a high level the process is like this
1. Get a Mammoth VPS with Ubuntu 11.10
2. In mPanel, Change its kernel to Finnix Recovery CD
3. In Finnix, start SSH and set a root password so you can scp
4. Boot your existing mail VM off a live CD
5. While using the live CD, transfer the data to the VPS. There's many options; to transfer the whole disk
dd bs=64k if=/dev/sda1 | ssh
[email protected] "dd bs=64k of=/dev/xvda". Another option is to wipe /dev/xvda on the VPS with mkfs , and then rsync
6. In Finnix, mount /dev/xvda /mnt ; chroot /mnt ; vi /etc/fstab and edit to suit (eg, replace /dev/sda with /dev/xvda ) , vi /etc/network/interfaces and edit to suit.
7. In mPanel, change the kernel to 2.6.32.12 and with any luck it will boot up.
If you have multiple partitions on the existing VM your best bet is to mkfs on the VPS, and then rsync everything into the single VPS partition