NATO is good, and comfortable, but kind of a pain to take on and off. I really prefer a nice leather one-piece strap. This one I found at watchbandcenter.com (a German-based company), for all of $22 including shipping. I just tried to search for the item to give a link, but the black ones must be out of stock. You can search for open-end or one-piece straps on their website.
I found this open end strap a while back when I was looking for a strap for a Hamilton U.S. military issued watch with fixed lugs. I really like the screw down end holder. http://forums.watchnet.com/index.php?t=tree&goto=563025&rid=0