I too had noticed that he disappeared from the directories in those certain years, but I didn't know where to look elsewhere. I know that after Agnes died, he remarried and settled in Bayonne, NJ by 1870. But there are no available directories online to check. Until finding this probate record, I had no idea that they would have been in the Town of Union. And I can't find the appropriate directory for that town. I thought it might be lumped in with Jersey City's -- but it doesn't appear to be. Perhaps Weehawken?
I'll be in Manhattan for a while in June, so I might just cross the river to see what I can find there.