I have this problem on my K3 (and previously on my DX) and I just cannot understand why Amazon refuses to fix it. There is a work-around - I'm afraid I do not remember whom I should credit, sorry - that involves disabling the index. Unless you have a need to frequently search within books, there's no real downside.
At the home screen, press del to get a text box. You need to do this for each command.
Type ;debugOn then press enter [Capital O; the text-box will disappear, nothing will appear to have happened]
Check debug status by typing ~help. This will list the debug commands.
Enter the command ~disableIndexing [capital I] and enter
Finally, enter ;debugOff and enter. Check by typing ~help again. If you get a list of commands, then debug is still on, otherwise your k3 will search for this string.
Debug and disableIndexing do not persist across reboots. If you make a mistake or just get lost, simply do a reboot to get back to normal.