Is there any way to recognise or anticipate which verbs require genitive instead of accusative?
I don't really know a why other than memorization. In Polish, if we are not sure, we ask questions: for Genitive it is "kogo? czego?" and for Accusative "kogo? co?" - but I don't think that's really helpful for a learner.
I tried "czy pan szuka", but I guess that's not what is sought.
Well, but it should be accepted. Added now.
And here's another. I offered, "Czy pan szuka tamtej kobiety?"
Of course, added.
So it takes genitive?
Yes, "szukać" is among those verbs that you need to memorize, it takes Genitive.