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).
Ebay - if you can figure out the thread size, it's often the best/cheapest way for small quantities of stainless bolts.
I had a problem finding a replacement bolt myself recently, including stopping at a local bike shop (which claimed not to have them) and did some searching--a good source I found was Bolt Depot. As for keeping the bolts serviceable, one thing you may want to try is coating most of the bolt (including the hex recess) with a quality paste wax. While it won't prevent most wear, it will help prevent corrosion of the threads and seating surfaces.
And, last but not least, apply thread lock, as mentioned by Gary above.
You can just look at the data sheet for the screw type and pick them up at your hardware store or go to your LBS and pick up something like the Sunlite Cleat Screw pack.
It looks like you need a countersunk M5 x 11.5 mm (which could likely be replaced with a M5 x 10mm or M5 x 12 mm which are easy to get at Home Depot - I'd probably go for the latter).