g1smd - 4:20 pm on Nov 20, 2009 (gmt 0)

They should technically exist 'forever'.

In practise they could be removed once they get zero traffic from both visitors and spiders AND when there are zero incoming links with that old URL anywhere on the web.

I would wait a few years after the last visit before removal, as there are sporadic reports of Google re-crawling very old (no longer existing) URLs after a gap of many years.