Have raised a ticket with Vidahost in hope they have more clout to get issue resolved. Have you done this too? After all not in Vidahost's interest for their clients to be inaccessible.
Vidahost have a bank of servers to host domains on and it looks as though you are also on the same server that we are on which is ns31.sovdns.com This server seems to be the only one that TTB cannot see despite a trace route from other community members from their ISP completing.
To us Vidahost have offered to move our hosting to one of their other servers which TTB can see. The implications of this would mean reconfiguring all our email clients with the new server address, no mean task. But the sting in the tail would see all historical emails being duplicated in Outlook.
Least pain for us would be to change ISPs but a migration can't be completed until after Christmas, requires a migration fee and entering into a new 12 month contract. The ongoing monthly fee would be about £10 more against TTB prices. And all because TTB cannot provide routing to ns31.sovdns.com - it all worked fine until two weeks ago, so what has gone tits up?