Just to be totally clear — you've explicitly done a lookup against their resolvers for a record that is not in flux and received a TTL higher than what the authoritative servers give out? Any chance you could post their name server addresses?
In the case of Virgin Media, they have transparent proxy caching on some parts of the network I believe, so it's possible this caching was happening there rather than on the DNS servers themselves.