OK right, tell me are you still paying every month? In a way, if you are then that's actually good news in the long term. Firstly the new contract is perfectly normal, contract is to supply a service to a particular address, not to an individual, new address, new contract, although in this case the terms of the contract are, or at least should be altered to reflect the length of time left on the original contract - this sometimes get 'overlooked', shall we say, but we'll cross that bridge when we come to it!
So, effectively, you moved and VM confirmed that they can supply the same service at the new address, fine. You move but discover that you actually have no working service at the new address even though you gave VM (presumably) adequate notice, yes. This will come under 'continuity of service' so it is equivalent to you still being at the old address but the entire provision has failed. In this case you are entitled to £8.40 per day from the day you moved until you either cancel (incidentally, how far into the minimum 18 month contract were you) or VM connect you up?
What I would be tempted to do is firstly DO NOT cancel any Direct Debit, let VM take the money for no service, yes I know it sounds bad but trust me. Secondly set yourself a deadline, ie if it's not installed by x date, then you'll kick off properly, in the meantime can you sort out a temporary connection, a 4G/5G setup on a rolling monthly contact to tied you over maybe?
When the deadline passes and you have had enough, you raise a compliant in writing to VM at their Sunderland office, demanding an immediate release from contract without penalty, a waiver of the normal 30 days notice, payment in full of the £8.40 per day, and £75 as recompense for the poor handling of your case, lack of any meaningful communication plus the need to make temporary alternative provisions.
This complaint will be treated with VM's usual degree of care and attention to their customers, ie it'll be ignored or you'll be told you aren't entitled to anything or offered a 'we're really sorry about this and feedback will be given, now do one', sort of response. If and when this happens, that's fine, just reject any 'resolution', demand a 'deadlock letter', this request will also be ignored, wait eight weeks and then escalate it to the Ombudsman service, and when you petition them, you ask for all the above plus £150-£200 compensation for their wilful refusal to allow you to leave, failure to pay the OFCOM mandated compensation and the inconvenience you have suffered by having to escalate it.
Unfortunately, right now, VM haven't actually done anything wrong, the forum team have absolutely no insight into nor influence over when or whether or not you get connected. The Ombudsman service have no power to compel VM to do anything at all, until and unless they fail to pay the proper compensation owed as per the regulations.