I couldn't find the key either, even though I knew it was supposed to be there. It is fortunate we start off with fireballs, as the door seems impervious to everything else.
I think they changed its location in the latest build:
The key is now dropped by Pontius Pirate
