Part 1: Nope, search has always been a bit ideosynchratic, and is currently suffering from server overload. Don't bother with it. (If you really need to search sites in dmoz use the Google site:dmoz.org) Part 2: Well, it depends. Search may be overloaded, site may have been removed for on reason or another (think not responding, domain expired, content changed, content no longer meets current guidelines), or it may have been moved to a more appropriate category.
Part 3: There is no category for all the travel agents in the world. You have to be looking at a specific sub set, usually by Region. Ah, you mean Recreation/Travel/Travel_Agents/ which says in the description "This category only lists global travel agency chains. All other travel agencies should be submitted to the appropriate Regional category according to the city or town where the agency is located."
Those @links such as Europe@ are to categories which contain the Travel Agents/Agencies based in a specific continent/country/region/city/suburb.
[dmoz.org...] may help explain site placement.
