Losing hope in securing a decent postdoctoral position
People on their second postdoc don't automatically look better than first postdocs just because they have more publications. Second postdocs are seen more as known quantities, but many institutes like gambling on the promise of new PhD grads, so you won't be compared to them in terms of straight publications. Your letter of rec will carry more weight, while their track record of publications will be considered more. The Columbia grad would give me more pause, but there are still many factors to be considered beyond exact research match.
Still, I think overall you have hope as your search has generated a lot of interest from nice places. Talk to your advisor about whether you can get a paycheck somehow at your current institute to tide you over through the job search, and about whether you should be expanding your search to include less prestigious places. If you're coming to the end of the line, your advisor will hopefully tell you that too (though ask around with other senior people for a more well-rounded view).
In some fields, no job by graduation basically weeds you out. Others have qualitatively similar deadlines that fall on different dates (for example a year gap from the PhD with no new position). Some fields are more flexible. Talk to people in your field about whether you're continuing a fruitless search past the point you would be expected to have been placed. From what you wrote you don't sound like you're there yet.