I've manages to find the answer on another forum. I'll publish here in the hope it may help someone else.
Create and send a text message to 789333 with the word "yes" (without quotes) in the text body. Wait 30 minutes, remove battery (with machine on), wait 10 seconds, insert battery and let the Blackberry reboot. Setup your email as usual.
Why Virginmedia couldn't put this on their website is beyond me.