while it is not "actual rule", many verbs that require genitive have a vibe of negativity: potrzebować(need), brakować (lack), szukać (search), nienawidzić (hate)
It's Genitive. Szukam kogo? czego? (I search for whom? what?)
But as for the 'why', I don't know if there is any good explanation. Obviously, we Poles just know that it's Genitive (and if not, we check what questions does the verb answer, as above), just as you know what English grammatical construction to use. So we remember which verb takes which case (sometimes different ones depending on the context). I guess foreigners, at least non-Slavs, just need to remember...
But maybe there's a possible help in remembering if you think of it as a "Search of parents", even if that's not grammatically correct?
If I negate a verb that takes the genitive, is it still genitive? So would Nie szukam rodziców be correct?
Nowhere. In Polish you use a lot less possessives than in English. Especially with family members. You just assume that the family member belongs to the subject of the sentence. And if it's not the case, then you specify it (Ja szukam twoich rodziców = I am looking for your parents).
But this sentence could just as easily mean "I am looking for the parents" or just "I am looking for parents", correct? Provided the context was right?
Yes, those are also accepted versions. But "my parents" seems the most probable.
Could this also be why when you make the accusative case negative, the direct object becomes genitive too, for example "nie widzę tej kobiaty" ?
"Why" = "because of the negativity"? I don't think there's any reason other than "it just is that way", but if it helps you remember... then why not ;)
"I seek my parents" is wrong because it doesn't say it's "my" parents? Because "seek" means exactly the same as "look for" and is a real cognate of the Polish.