Cache lag on NS change for 5 days ??

[Dave]

The nameservers on micouriers.co.uk were changed to a new hosting
service recently (according to nominet.org.uk on July 31st).

With my ISP (telewest.co.uk) the change was finally apparent Sunday
3rd August. The broadband ISP that the micouriers people use, FirstNet
(http://www.firstnet.net.uk/), has apparently still got stale data in
their cache, and so in the office they can't see the site or receive
email from the pop subdomain.

A tracert micouriers.co.uk on their office computers won't resolve.

I can 'fix' this on Win clients with the Hosts file, but I want to
track down what's wrong (the support people at firstnet are no help).

Surely a 1 day TTL (nslookup with server ns2.gradwell.net) shouldn't
lead to 5 day old data? Do the records for the domain look ok?