I think the value of
backlinks via listings in quality directories has been established. If you're not convinced by your own experience or by the comments all over Webmaster forums... then I'll let others try to make that case.
A lot of people rightly question the usefulness of directories and whether or not the traffic is going to amount to anything of value to the advertisers (listings).
First - value for the advertisers:
I think the value to an online retailer of flip flops, to go along with your search example, is going to be almost 100% the SEO value in helping the flip flop retailer in the SERPs so when people do search for "pink flip flops for guys"

their site will show up further ahead in the results.
In addition to being an important place to be for regional oriented sites I believe listings can be of great value in vertical industries when business people browse through business categories and directories reviewing the companies listed. The value of a new partnership or gaining a new supplier or client can be of tremendous value over the lifetime of that new relationship. So I believe the value of listings depends in large part on the type of business or organization.
Second - value for visitors:
Again it depends a lot on the quality of the directory (quantity of listings, quality of listings, ease of use) AND whose doing to browsing. One new relationship can be worth every dollar invested in every directory.
Granted, many directories offer too few listings to be of great use to visitors, but when you consider that most visitors are there because they're either considering a listing themselves OR as a result of spotting a competitor, vendor, or client's listing on a search result I think the case for making the investment can be easily made.
I hope this helps explain why many smart businesses (online and offline) continue to invest in directories despite the relatively light traffic.
Cheers
P.S. I assume you're a guy mxracer because of the way you're slamming your head against your desk! A girl wouldn't risk having a bad hair day....