I have had several quest monsters spawn on unreachable locations.  In the water, on islands, and even on mountaintops.

In theory, the first 2 problems are not insurmountable as you can raise land and reach them (though this may be inconvenient, especially for lower level quests).  Monsters spawning on mountains however, has no workaround as far as I know.  The monster cannot move (or at least doesn't), and you cannot lower land with a unit on it.

So far, I have had problems with fire elementals spawing in some event, a quest wherein spiders for a spider silk quest were on an island, and scrap golems from a temple appearing on mountaintops.