I have a magento install that has 10 store-fronts (maybe 10,000 products, 800 categories), when we reindex the URL Rewrites, we get 404 errors on all links until it finishes.
Is this standard behaviour? Is there a work-around?
That shouldn't be the case. What Magento 1.x are you using?