I'm currently in the process of converting from 5.5 to 10 so am guessing that my experience 5.5 is pretty similar.
Just to narrow down the possibilities...
How confident are you that the parent record disappeared? If there's is any chance that some action by one of your users can create an unmatched record in one of your child records it would also create what you describe.
Another option: Relationships require healthy indexes in order to function correctly. This is also true for finds and sorts. Sometimes files that have been in use for a while develop corrupted indexes. They will sometimes appear to function correctly until you spot one of the above functions failing to behave as expected. To rule this possibility out, you can:
Save a clone of your file and then import all records into your clone. Since you are dealing with v6 and multiple tables, do this for all the files concerned.
Perform a recover on the files and then test the recovered files. (Don't put your recovered files into regular use, use them for test purposes only. If you have to recover the file, import the records from the recovered file into a back up clone.)
Hope that helps