Tribute Merchants have been taken down temporarily, as they were rather out of balance. Apparently lot of easily farmable and accessible items gave about 1k of tribute points and stuff. SoE says they should be back around the weekend.
Anyway, I found a link to a listing of the NPCs:
http://necrorealm.gotdns.com/tribute.asp
Edit: Some are missing on this list, for example the Tribute Master I was sent to (Good aligned Qeynos Bard). NPC called Christian something, near the Paladin guild in South Qeynos. Seeing that some of the towns on the link have multiple NPCs within the same zone I think there may be one for Good and one for Evil aligned classes or something.
Using the 'Find' option on your Actions window (ALT-M) makes finding the NPC you have to visit easy.
Edited, Fri Feb 13 08:55:29 2004 by Marisha