It's not just the way this is phrased, it's that there is no English-language formulation that works at all. Swap "shirt" for "tie", because paisley is quite common on ties. Now, try:

* tie without paisley * tie not paisley * non-paisley ties * ties that aren't paisley * ties other than paisley

You guessed it, in each case, at least half of the results are paisley ties. The only way to actually get what you want -- the set described by X, minus the set described by Y -- is to use the exclusion operator in the search, "ties -paisley".

This is great, and makes intuitive sense to somebody with multiple computer science degrees. But not only is it hard to explain to an outsider, it's actually quite hard to get them to think in a way that accommodates this capability, that is, in terms of set theory.

I don't agree. Paisley is a well-known pattern type and some people really dislike it. "Shirt without paisley" is not a common request but its meaning is clear (if you do an image search for paisley you get lots of fabric images, so it's not like search engines don't know it.) I'd say the same for "shirt without red buttons." In general the pattern <article of clothing> without <feature> shouldn't be that difficult for search engines---especially since many are tuned for consumers.