Yes, search navigation on e-Ink devices is slow and cumbersome. I'm not sure what the solution(s) might be. Maybe a thumbnail view of 20 or 30 pages on the screen. Sometimes we remember what the general layout of the screen looked like. Some readers allow you to use shortcuts to jump 10 pages at a time, like the Sonys. The Kindle DX (not sure about the K2) allows you to use the 5 way button Left to jump to the current or previous chapter's first page and the 5 way button Right to jump to the next chapter's first page. There are probably already many shortcuts built into any reader if you check the forums. But we really could use some better functionality.

Sadly nothing beats the old dogeared approach of a printed book. But with some imagination I'm sure they could greatly improve reader navigation.