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.
It is correct, it's a polite form. Please report it next time. :)