Cache Size has nothing to do with it.
a cache with just 1 line and your old address, will never refresh until the default TTL in the cache expires.
Looking at this
kb article (XP & better only), it appears
• The default TTL for positive responses is 86,400 seconds (1 day).
• The TTL for negative responses is the number of seconds specified in the MaxNegativeCacheTtl registry setting.
• The default TTL for negative responses is 900 seconds (15 minutes).[/b]
So maybe it was not the cache afer all, given default TTL is set to *just* 15mins for a negative response.
More reading on the windows