Without fail, a company will employ a recommendation engine for a purpose (nobody does this for fun, really). Often, that purpose is profit (or something along those line). For most companies, ‘relevance’ is irrelevant (no pun intended).
The success of any recommendation engine should (in my opinion) be measured by its ability to meet the objectives it was intended to achieve. As said, in most cases, this will be tied to sales or profit.
A/B test your system against a control (often random, might be rules). If your recommendations increase sales (or decrease costs, or decrease call handeling time, or increase revenue, or increase customer satisfaction, etc) compared to the alternative you’re doing pretty good. You can forget about the rest.
Who cares about relevance if you can measure business value?
[ Posted on Quora as answer to What is the best way to test the relevance of a recommendation engine? ]