I am under the impression that all transactions less than 0.01 require the fee.
And to your point, the smaller transaction amounts are the very essence of the problem. Even though I want to continue to sell things for a dollar, that fee is only going to go up. Right now it's seven cents. by year's end it will probably be more like 10 or 15 cents. On a decent sized transaction it is negligible. but at $150/BTC and rising, it's real money down in the dollar store section.
Yes. You're correct all outputs must be greater than 0.01 to and under 10k (or 1k?) to be zero fee.
So the best possible solution I see for you in this scenario is not doing a typical checkout where they fill a cart and then pay you. Instead I would suggest doing something along the lines of them funding their store account with "item packs" these item packs can be nicely sized in normal denominations ($5,$10,$20, etc). You can have the 'frugal' option be the lowest dollar amount that would get them up over 0.01 btc (right now 2 dollars).
So maybe a user is 'forced' to get a couple of extra items on your site (or save those credits for later). . . I doubt it will deter people from shopping there...