The wording seems strange, why would someone want to 'steal' a network card mac? It sounds more like it's the modem's mac that's been stolen. Doesn't the nic mac just govern whether Virgin dhcp dishes you out the same ip if it's still in the pool? I suppose I can see how that would produce the same symptoms as you're describing though.
If it really is the network card then it's possible to change it by editing the registry or use some software e.g. :
http://www.codeproject.com/KB/applic...IdChanger.aspx