Most comments already told how good this card is. I just discovered that it's a favourite of mine comined with [Greenwood Defender]. Let him chunk 1-2 Attacks, revive him, let him do it again. Awesome for keeping attackers up.
Note that, due to the difficulty to properly combine Messenger of the King with the intent of this new contract, we at ALeP we have proposed a new wording for Messenger of the King inside our Free to Choose List, that you can find at this page alongextendedparty.com
The new wording of Messenger of the King basically turns the MotK hero into a starting hero in all respects, so if you want to use MotK with say At the End of All Things, the MotK will be one of your two starting heroes with all that entails (like not being able to gain resources from attachments). The same would be true for something like The Grey Wanderer or Bond of Friendship, with the MotK hero taking the place of a starting hero.
I'm surprised that as of this writing, none of the reviews on this page have mentioned Lórien's Wealth yet, because that's the first card that I think of when I think of Gandalf's Search. As soon as I saw the two right next to each other in the (revised) core set, I wondered what the use of Gandalf's Search could be over Lórien's Wealth. It may be the only way in the core set to pay 1 resource to draw 1 card, but paying 2 or more resources to only draw 1 card makes this card lose to Gléowine and Lórien's Wealth, which are both also from the core set. And rearranging what's on top of the player's deck is not what you want to be paying for, because having cards in hand is much better than having them on top of the deck. As a matter of fact, for many of the game's first cycles, there were barely any cards or scenarios that cared about what was on top of your deck; and by the time those scenarios and cards started becoming more common, we had already gotten much better deck rearrangement options (Imladris Stargazer and Wizard Pipe to name a few). The only time I have ever used this card was when playing the mono- starter deck from the revised core set, and that was only to pay 1 resource to draw 1 card.
I did see a comment on a Youtube video a while ago (I don't remember which video) where the commenter had made a house rule alteration for Gandalf's Search: it costs 3 instead of X, and lets the chosen player search their entire deck for any card rather than the top few cards of their deck. Now that made me think. If that were how the card worked instead of what we got, I wonder how much more play would it have seen? Would it have been worth it to use a deck slot and pay 3 resources to choose any player to search out their combo piece? And, on the other hand, would it have been healthy for the game to have a deck-searching card right from the beginning? But I'm not a designer.
Ah, the Hungry Creature! Bane of riddlers everywhere, always lurking, waiting to gobble all the cards in your hand... or an unlucky hero.
Anyhow, can I discard an encounter card that's in my hand, such as "Lost in the Wild", as a 0-cost card? Lost in the Wild says it cannot be discarded by player card effects, but Hungry Creature is not a player card.
While this is an excellent card and should be included in most Lore decks, I disagree with those who say it has no drawbacks and should be included in every single lore deck. Some decks needs to have a high number of allies for certain cards to hit consistently (ie A Very Good Tale) and another example is Zigil Miner decks, where you may want most cards to cost the same amount. While these drawbacks will still rarely outweigh how good this card is, they are still worth consideration.