I can relate. I have many who were in the city directories but missed by the census. My current project is my great grandfather William Henry Armstrong who, according to his death record, was born in Bay Ridge sometime between 1858 and 1862 depending on which source you choose to believe. The death cert shows his parents were James Armstrong and Mary Rankin, both Irish immigrants. But I have as yet to find anything on William prior to the 1880 census when he was out on his own. I've got lots of theories but no proof. I see a couple of William Armstrongs living with families of other names in the 1870 census which could mean either his parents died or he was just sent out to live and work with/for other families. OR, he was with his parents but they were missed by the census.

But even he isn't my toughest. I have a great grandmother from Pennsylvania who is/was a world champion hide and seek player. She was there in the census and city directories until 1900 (In PA) then vanished. 5 years later I find a record of my great grandfather's second marriage and his divorce being final 2 weeks earlier. He didn't file it, so she must have, but where, I don't know.