The key is not in the castle.
In fact, it's not on the castle grounds.
It's in the Wizard's Hut.
The key is on top of the chairback.