Hmm, he's supposed to be near the throne in the big castle with all the Paladins. I've never experienced him being anywhere else. Did you ever give a teleport rune to Lee? I know Lee will attack the King if they ever meet, so I suppose they could have charged off somewhere while fighting.

Other than that, the only real option is to summon him or the item you're looking for with a console command. I think he holds the Scepter of Varant or some such thing which is needed for the main quest. Based on this page (http://faqs.ign.com/articles/768/768307p1.html), I assume the correct command is:

spawn It_Scepter