I've done six of these on my and friend's trucks, all at just over 100K, and every one of them looked almost new when I took it off. I wouldn't do it 'til 90K at least, if not more. One friend is at 140K and we took the upper belt cover off to look at it, and it still looked fine.
I would go with OEM, just because Toyota does such a good job in the first place, why mess with it. I've ordered from Toyota of Dallas, and they are great (good prices and good service). I've also ordered from this place
http://www.toyautoparts.com/TAC-4WDV6-002_1999_parts.html . It is very cheap and the parts are OEM, but it's strictly over the net and their customer service is nonexistent. They're fine if you know exactly what you need, and they do have kits
The new water pump will come with a rigid gasket. They are better than the Toyota gasket material. There are also ways to compress the hydraulic tensioning piston without taking it off the truck (which requires removing the AC compressor-and is a pita).
Good luck.