Here is my current idea for the power search and replace dialog (click to enlarge):

The shortcut keys (underlined letters) must not conflict with those used by Kate's menu, which became a little tricky. I am wondering how we will solve this problem for other programs using KatePart - what if they use some of these shortcuts for the menu? Here is the updated Firefoxy one:

Comments welcome.

[EDIT]: Dialogs were just "drawn" with Qt Designer — they are not integrated yet.