Yeah, I've had this same issue. As you alluded to, the negatives function as broad negatives would in Google. I don't believe there is a good work around outside of bidding down your broad match keywords to fend off the irrelevant clicks. It's not exactly a good way for Microsoft to maximize ad revenue.

I actually had an even worse example. In my situation, I had an ad group of Black Shoes keywords and just the search "black" was triggering my ads. That query was racking up clicks pretty heavily too so bidding down/pausing the broad terms was the only solution I could come up with.

Did you try to use only phrase match for your keywords?

But I confirm that 'shoes' as negative will exclude everything that has the word 'shoes'!

I don't want "shoes" to trigger my ad, but "black shoes" I do.

That shouldn't ever happen. If it does happen, it's a MAJOR glitch. According to adCenter: "Broad match triggers the display of your ad when individual words in your keyword appear, in any order, in a customer's search query. For example, your keyword "black shoes" would match search queries that include "black shoes," "shoe is black," and other variations, and not just "black" or "shoes."