Win XP SP2 (all updates applied), ie7
I've already tried all of the suggested solutions.
Advanced Search gives the same error

Wait a minute
I just found out that search works when i try it on another (test) database so it has to do with my main database (which i must say is quite big and slow) i suppose.

I just compacted my database and everything works fine (and quicker)
!!! Problem Solved !!!