They only rolled the feature out to all shards a few days ago:

We are aware of the time out issues with Vendor Search and we working to resolve the issue. We should have Vendor Search up and running no later than 10 am EDT tomorrow morning. Thank you for your patience with us.

We appreciate any feedback you may have with this system, please email uo@broadsword.com.

I guess new features that test well on a smaller scale can sometimes break down when subjected to a larger user base.

Anyhow, this post was published to the UO website a couple of days ago, so I can only assume that a patch for the issue has been pushed out. There hasn’t been any word to that effect, however, so don’t be surprised (either) if the problem persists in the game.