Someone I know who runs a moderately large website told me that some ISPs cache DNS for as long as a week without regard to TTL.

We track DNS disobeyers at Google, as we use it for load balancing (along with many other large sites).

I'd be kind of surprised if any large/professional ISP disobeyed the TTL that badly, because it would cause frequent problems reaching popular sites like anything hosted on Google or Akamai. But randomizing the DNS request isn't a bad idea.