You might want to ready my answer to this question on Quora: http://www.quora.com/If-I-have-a-website-with-millions-of-un...

Where I explain how we did this at eBay when I was working there. eBay is quite unique from the fact that millions of new URL's get created on a daily basis, with a short lifespan.