I think the explanation is that there's no good records in the future. They know of a "Sarah Connor" but don't know anything about her other than what city she lived in. They don't know who she is, who her parents are, or anything like that.
If it was possible to change history via time travel, they really wouldn't even have to bother killing Sarah's parents. If they go back far enough, they'd prevent her ever being conceived. There's only about a 1-in-100,000 chance that a particular sperm will fertilize the egg. If they did anything to change the exact moment of conception, a whole other person would be born. So all the Terminator would need to do is interact with the mother or father at any previous point in their lives, or anybody that might possibly interact with the mother or father at any point, and you'd have Joe instead of Sarah. Of course when you play with that fire, you also prevent the people who build Skynet from being conceived, which would be bad news for the robots.