Yes it is singular, genitive.
Because you need genitive after szukać.
(My interpretation - because NIE MA JEJ , and we need to JEJ SZUKAĆ,) - as you probably know negation usually needs genitive
Well, "lady" is not a basic word, while "woman" and "kobieta" are totally basic...
Also, "lady" isn't even as popular as "pani" in Polish.