For Windows, you tell them they need to order recovery CD/DVDs from the manufacturer, and then we order them for them. It's usally between $15-25. If we happen to have restore disks from their manufacturer that will work with their model, we use them, so long as the computer had a valid copy of windows on it to begin with.

If it's a computer they've built rather than bought from a big box and have lost their key, well, they're out of luck, but most people who build their own computers don't bring them to a computer repair shop.