Have you checked out Lotus on Red Hat?
There is a trial version Live dvd of IBM/Red Hat Lotus Notes referenced here:
The lack of a good desktop search integrated with lotus notes is a serious impediment to taking linux up in my workplace.
Red Hat Enterprise Linux isn't free, and I don't know the extent to which Lotus Notes is integrated, but it might be worth looking into. There might also be possibilities in CentOS, which is a debranded Red Hat without the support.
Edit: What about Google Desktop - apparently it will index anything, including Lotus Notes.