some towns their in random places while others they can be found in the same place. I at times cannot locate the vendor either. Not much else to do besides run around holding the Tab key. I've found them behind doors before, or outside the castle walls. If you have to goods to deliver no one else can get the job. So no worries about that. Once you get the jobs goods, it will drop off the listing so others aren't going there looking for work.
I never had a person I couldn't find once I had the goods to deliver. Typically I have trouble finding the jobs giver. Best i can offer is look harder.