The biggest problem with Tribute is its unpredictability. It's hard to build a strategy around a card when you don't know what it's going to do. The way I see it, there are 2 things that make it useable:
1. Opponent is building a homogenous deck, so you can have a reasonable expectation for what it will do (e.g. vs near-pure-BM it gets you money and sometimes cards, vs scrying pool it gets you actions).
2. There are dual-type cards, so it can potentially give you 3 bonuses instead of 2. This particularly works with Nobles, because Nobles also have some versatility. If you get the actions you need from your Tribute, you can play Nobles for cards, but if not, you can get more actions out of Nobles if needed.
Presumably deck-top inspection like Spy could help, but I've never actually done it. For anything other than Scrying Pool, it seems like it's going through too many hoops for something not that great, but then again, if there's really nothing better on the board than Tribute, you might have the time to actually get it going...