Since I asked my whole question in the topic I will just pre-thank the rules Maesters!
Do you have to pay an out of House penalty for using At the Gates to get an out of house Maester?
You never pay the out-of-House gold penalty when putting a card into play. You only do so when you are playing the card from your hand. "Play" and "Put Into Play" are completely separate mechanics, and the OOH penalty rule only talks about "play."
However, on this specific card, you may want to look at the FAQ:
(v2.4) At the Gates F20
Should read: "...search your deck for a neutral
or in-House Maester character of printed cost
3 or lower..."