Did a little further research. All the research to be done is manual, in a large set of card catalogs. Yep, little bits of paper. See the copyright office linky about it here....
http://www.copyright.gov/circs/circ23.pdf
So, using the Heinlein example...You would have to go to Washington, DC, go to the card catalog during business hours, and look up the publisher of Startling Stories, find the card for the year published, and write down all the info. Also you would check to make certain that there was no entries for the individual authors for the stories entered.
So far, so good. Now you skip forward 28 years in the card catalog, and do the same look-up. If you don't find an entry for either the publisher or the author, then it's probably P.D, at least for that variant of the story.
Why both the publisher and author? Because if the author convinced the publisher to revert the rights back to the author, it would then be the author holding the copyright to be renewed.
This is all theory to me, I've never done this....