You missed one possibly vital argument to
--hard-links. It depends on the distribution, and I guess it's different now than it is in the past, but system directories and/or files (more so than user files) can easily be hard links to others. For example, in the somewhat recent past on Archlinux,
/usr/X11R6/bin was a hard-link to
/usr/bin. At present, I couldn't give you concrete examples of how it would be today. You could look into it.
You may also have lost vital information by putting it into a
tar.gz. Does it store ACLs? Would it have stored hard links?
You also missed
--sparse, but that's merely an inconvenience.
To restore it, I'd boot a live CD, or some kind of rescue environment your VPS provider gives you. You can then just untar the data into the root partition, chroot into it (with bind-mounting
/sys) and running something like
These options can vary depending on your setup.
Edit: since you may have access to your original VPS, you can do something like this:
pv /dev/vda | gzip --fast | ssh email@example.com "cat - > imagefile.gz"
And then on the rescue environment on the new host the reverse:
pv imagefile.gz | ssh firstname.lastname@example.org "gunzip - > /dev/sda"