Amazingly, since along with airlines and insurance company the travel industry was one of the first to embrace computers, there appear to be very little available for the travel agencies! I found no templates, but the following link is for a commercially available database. They offer both single user and multiple agents options, with a modest, one-time setup fee then a modest monthly fee. The big plus is that they're responsible for support if things go awry, as well as doing updates as travel rules and regs change, which in light of 9/11 could be often. Hope this helps!
http://www.clientease.com/