Direct Debit guarantee - if money has incorrectly been taken from your account, your bank should be able to ensure it's refund. Have you contacted them?
If you cannot get any resolution to your complaint from Virgin Media, then contact OFCOM as the regulator.
VM aren't good at paper. Unless your letters were recorded delivery so you can p[rove a receipt they probably ended up in a black hole somewhere. You may first wish to try the CEO's office at Virgin Media to see if they can cut through to the problem
neil.berkett@virginmedia.co.uk