Is there some fairy tale out there where a princess solves a quest by getting swallowed by a while and vomited onto the only island in the area that has what she needs? How did Rosella know that she needed to do that?

Not a princess, but Pinocchio is the first that comes to mind (without Googling). There are probably others.

Back to KQ4, it was simply an unfair game with badly designed puzzles. During that era, Sierra's philosophy on game design was to have the player explore and scrutinize every detail on every screen and discover as much as possible, and then work out the proper sequence of actions to actually solve the game. Plot be damned; the puzzles didn't have to serve the plot as long as they prolonged the game and made it seem harder.

Therefore, the only people who "solved" this puzzle you're referring to were seasoned Sierra players who knew how to play through this design framework and discovered that desert island (and what's found on it) completely by accident, as well as those who bought the hint book. KQ4 and KQ5 both have many puzzles like this, but this one in particular is probably the most egregious in the entire series.

Actually, the puzzle that is considered the worse is having to spell Rumpelstiltskin's name backwards in the original AGI version of KQ1. You didn't just have to spell it backwards, but you also had to use reverse alphabet. Roberta later admitted that the puzzle was unfairly way to hard and made it simpler in the updated SCI version

I agree that was a very absurd puzzle in KQ1 AGI. However it's not unfair because there were at least some clues, albeit tenuous, that pointed to the correct solution, and one could still progress further and complete the game upon failing to answer it correctly.

Whereas in KQ4, the player was completely stuck in the first act of the game, unable to progress further, with no hints, tenuous or otherwise, what to do or where to go next. Not until endless wandering and explicit searching does the player happen to come across the solution, and by accident. No amount of adventure game skills or knowledge of fairy tales does any good whatsoever.

And on top of that, the game can be unwinnable even when you get inside the whale (if you don't have the feather or the dead fish), and how the hell is anyone supposed to know that you can swim to the west, let alone that you NEED to swim to the west before you get to the whale. Also who would feel comfortable trying that anyway when there's an inescapable shark? I think I agree with codefenix on this one since as bad as the Rumplestiltskin puzzle was, at least the game isn't unwinnable if you don't solve it. That said, there are a number of puzzles in "King's Quest" games that can be considered the worst puzzle ever (bridling a snake, throwing a pie at a yeti's face, giving a genie bottle to a witch even though the only way to know that it's a genie bottle is to open it yourself and die first). The cave in KQ4 is also one of the worst things ever. The troll is inescapable except when you first enter the cave and having a chasm in the middle of a cave where it's almost impossible to see anything even with a lantern was a mean move by the game.