Is Kubuntu one of the KDE distros that you have tried? It has worked well for me so far. Although I'm running it in VMware Player on my work laptop. I have Debian sid on my home machine.
For desktop search I'm using Kerry Beagle. It's a KDE front-end to Beagle. There's still a lot of room for improvement, but it's fast and seems to work pretty well. Kat looked like a very interesting project, but the website has been closed everytime I have checked in the last few months. It's a shame. I was really looking forward to someone developing a Konqueror integrated front-end.
What OCR apps have you tried so far? I haven't actually run any myself yet.