Faith just sent me a link to endless, pointing to their faceted navigation. It’s a classical implementation in a left nav bar, but you can see that they put thought into each navigator specifically, instead of a one-size-fits-all approach. I haven’t used the site extensively yet, but it seems like it would work nicely.

Category navigator:

Brand navigator (multiple select as well as keyword search), color family, and shoe size:

Heel height and price:

One thing i’m not sure works well is their search state breadcrumbs. They are in the left nav, where you selected them instead of somewhere more visible.