As seen in quite a lot of video games:
What is the meaning/origin of this phrase?
The older meaning of fast, with an example dating from the 9th century, has to do with things being solid or firm.
The first OED definition is:
I. Firm. a. Firmly fixed in its place; not easily moved or shaken; settled, stable. Obs. or arch. exc. as said predicatively of something fixed as in a socket (e.g. a nail, a post), where the sense approaches 4.
There are seven senses in which this is used with multiple sub-categories.
It is only when you get to sense 8, that the meanings take on anything to do with speed. And compared to the year 888 for fast meaning firm, the speed sense has its earliest example from as recently as 1400.
To be stuck fast simply means to be completely stuck and too rigid to be manipulated (here's a source). Furthermore, fast generally can mean (this is one of the alternate definitions of the word you'd normally associate with speed) firm and resistant, which means stuck fast isn't some anomalous phrase in which fast takes on a completely new definition, but rather a simple combination of two words correlated in meaning.
In terms of origin, perhaps rather surprisingly, the modern, most common definition qualifying something's speed actually came after the original definition, which is in fact the one in stuck fast.
Here's an excerpt from dictionary.com:
Old English fæst ‘firmly fixed, steadfast’ and fæste ‘firmly, securely’ In Middle English the adverb developed the senses ‘strongly, vigorously’ (compare with run hard ), and ‘close, immediate’ (just surviving in the archaic and poetic fast by ; compare with hard by ), hence ‘closely, immediately’ and ‘quickly’; the idea of rapid movement was then reflected in adjectival use.
It simply means that the door is stuck very tightly and is otherwise unable to be opened at all.
From the Macmillan Dictionary:
unable to move at all
Video games will say this to suggest that there is no way you would be able to open the door, even by force. Saying stuck fast dissuades the player from becoming annoyed at the game; if the door was just stuck, why couldn't our space marine ram it down with his shoulder? It's because the door is stuck to the degree that it really can't be opened.