There's a difference between creatures that have spell-like abilities (which is most magic-using monsters), and those that actually cast spells (which is just a few of them).
I think I figured out the problem I was having. Really, before any encounter, the DM should have prepared what spells are available to this guy - the brilliant thing about this creature is that there is no real limit to how many spells of a given level it can know. However, I think this list of spells known should be picked out before a combat, both for ease of reference for the DM, and just to be more "fair and legal" to the players. I think the suggested random rolls from the original text were an easy way to set up such a list for the DM.
Really, we don't need a mechanic to determine what spells it can "try to remember" during a combat. If it remembers the spell once, it always will, and can always use it if it has the daily spell slots left to do so. So those spells on the known list are static, and what we really need is a mechanic to add more. What Shade has should be very well adaptable to this idea. Not sure that it needs to be a separate power either; this should work equally well as a paragraph under Spells.
" Sea hermits are sages of deep, undersea kingdoms who seek to trap the unwary in order to study their memories. Through arcane processes, these memories are extracted to teach the sea hermit new skills, spells, and reveal other information about the people who dwell on the surface. Sea hermits have no qualms about the deception they employ or the fatal methods of memory extraction."
Spell Memory (Su): A sea hermit does not possess a typical list of spells known like most sorcerers, nor does it gain new known spells automatically. A sea hermit learns new spells by taking them from the minds of its victims. A sea hermit learns a new spell from any spell list possessed by a victim (up to the maximum level it can cast) by making a successful Spellcraft check (DC equals 15 + spell level). Failure indicates that it cannot remember that spell. If successful, the sea hermit adds the spell to its list of spells known. All spells cast in this manner are treated as arcane spells.