Linode (http://www.linode.com) has again proven why they are one of the best (if not THE best) virtual hosting companies out there.
We had a problem on a virtual server where some critical directories were deleted by accident. Server was still running, but no login or ssh access was possible (the /etc/ directory was gone).
I logged a support ticket with Linode to get some suggestions on how to proceed. They reacted promptly with some good suggestions and even links to documentation on how to solve the problem.