To be fair, the first and last query would also confuse me if someone asked me for that item. "Shirt without paisley" feels a bit like "cereal without elephants." You don't usually explicitly exclude an element that is relatively uncommon.
* 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.