You are quite right, James—I overlooked the fact that it is the whole clause that is the object of the preposition, and that 'whoever' is the rightful subject of 'gave'. My answer was wrong.
"To whoever gave me this gift: thank you" is correct.
If anyone's interested, the grammar works like this:
"Whoever gave me this gift" is a fused relative construction. "Whoever" is called a 'fused' relative word because the antecedent and the relative word are fused together instead of being expressed separately as in simpler constructions.