I use UltraEdit for Windows and uex on Ubuntu 12.10.
Ctrl+F brings up a find dialog that can be partially, but not completely, navigated with [tab] presses.
Ctrl+H brings up the same dialog, but on the replace tab, still partially navigable with the keyboard.
Basic find works great. Ctrl+F, then "string to search for", then [Enter] selects your term. No need for a mouse. [Enter] repeatedly goes through your file for the next term repeatedly. This maintains focus on the dialog. You need to [Alt]+[F4] to close the dialog or [Alt]+[Tab] back to the uex window to continue editing the document.*
Replace is tougher because the dialog really requires a mouse to get full use out of it. Not every option or button in the dialog has a tab-stop. Like you mentioned, it was obviously not designed for keeping your hands at home on the keyboard.
* As I'm sure you're aware, Alt+Tab and Alt+F4 work in Windows and Windows-like distros of linux to switch and close windows. Linux has quite a few window managers to choose from and yours may differ.