Work will have much more in common with said open source efforts than with all those algorithmic challenges though.

A good chunk of these people will be good engineers that cannot talk about or show the stuff they worked on at their previous job. And those places specifically ban them from making apps or working on open source and they will be hard workers that work 40-50+ hours a week. Maybe they have kids too.

How do you interview these people?

I agree, algo interviews are annoying and I wish it wasn't there. If it wasn't it would make switching jobs a lot faster. But thats what it is. The suggested alternative of portfolio work has it's own problems, the same with homework problems.

Unfortunately, even places that have you write code with the internet still have an algo inteview or two.

I had an interviewer ask my for some code samples. Conveniently it was the day after I accepted another offer, but that was a definite no bueno for me, I don't contribute to open source, and I was hardly going to send them some code samples from my previous job.

Sure, but you need to be able to produce a work product example of some sort in lieu. Most people can.