I have more problems with those stupid things getting stripped than you would believe. (Just ruined a shoe trying to get a stripped bolt out.) Anyone know if I can buy just the bolts, rather than the whole cleat? That way I can put a new one in every time I have to adjust it or it comes loose to, hopefully prevent that from happening. (I mean the MTB recessed ones)
I usually ask my LBS when I need spare parts like that. You might have to pay them a buck or two, but a lot of places keep a small stash of parts like that.
If that doesn't work, they might be able to order the part directly from Shimano (or ask your friends).