I think you nailed the disconnect between our views.

What I personally am looking for is an engineer -- someone who can look at problems formulated in a fuzzy fashion (this is critical), figure out what technical solutions exist, probing the customer/user to flesh out the initially vague requirements and come up with a few different ways to implement this.

You are looking for coders: someone who can take well posed, unambiguous problem and algorithm descriptions and turn those into a working code. That is probably a better fit for a "coding interview" referred to in the title. It is just my experience that I get much better code and value for $ by hiring engineers even though I have to pay them higher salaries. That's just me though, YMMV.