Perhaps part of the difference between those who are satisfied/not satisfied with materialism is in what role something other than materialism could play here. I just don't get how any of the non-materialist 'answers' are more satisfying than the materialist ones.

The answers are satisfying because they're not really answers. They're part of a completely different value and belief system - a large, complex structure that has evolved because it is good at generating certain feelings in those who hold it; feelings which hijack those people's emotional systems to motivate them to spread it. Very much like the fly bacteria (or was it a virus?) that reprograms its victims' brains to climb upwards before they die so that their bodies will spread its spores more effectively.