"At Heroku, we discussed a real issue they were having and halfway through the interview we were both up at the whiteboard bouncing things back and forth, drawing things up. At the end of the Heroku interview we both knew how the other worked and how we would work together."

I find this kind of odd and correct me if you think I'm off because I'm not a programmer.

But for any company to give you a problem that they are having and for you to help them solve it... shouldn't you get compensation for that (outside of a job position)? That's basically free consultation. It's like how some companies give design tests for designers, which is basically spec work. Even if they don't choose you, they could still take some of the ideas and implement it.

It's one thing to give a general problem and analyze your problem solving skills and knowledge (as well as to verify your resume).