Looks like KVM has been a de facto downgrade. I never had constant small dropouts on Xen, and I had certainly never had my server go silent for hours. (Linode 2048, btw. It started as a 512.)
It might be time to go looking for a new VPS provider...?