I actually went to OVH a couple of days ago. I needed a new server and wanted to give them a try. But they're not accepting new clients anymore: http://www.ovh.co.uk/a1186.SoldOut

I didn't know about online.net. Shame I didn't see this a few days earlier. I would have given them a try.