Thanks to Jason this has been solved.
It appears many of the addresses had some oddities in them (descriptions of where the location was, not just a street number/name) which was likely causing Google to stall during the cacheing process. I though the Caching was done by Postal Code (Zip) but as Jason pointed out - that alone would not provide an accurate result so Google uses it all.