AG4Life - 8:29 am on Sep 19, 2012 (gmt 0)
Just an update to my situation, which has seen 4000-5000 new 404s being added every week. Some are the older links as I described, but most of the new ones seems to be of the format http://example.com/1345876986000, with a random number at the end (but always starting with 1345).
It looks like a unix timestamp with a few extra zeroes.
Google Product Forum thread here: