I have been using Virgin mail for about 7 years now with no problems (other than the colossal amount of spam in recent times).
Thanks to their new spam blockers and my own installation of Spam Inspector V4.0, my mail is now reduced from around 70-80 a day to a more manageable and relevant 4-5 per day.
I've had no problems in recent days while Virgin undertook the spam blocker installation, and am very happy with the service, especially now I'm on Virgin broadband.