Ask nicely for a laptop with no OS. When the reply is 'No', return/wipe the Microsoft default, carefully documenting your refusal of the End User License Agreement, and ask for your money back on the OS. (They'll still say 'No'.) Be firm, be persistent, and even go as far as issuing a Small Claim.
They will ultimately accede, because the law is on your side.
No one need pay the Microsoft tax.
To me that sounds like a whole load of work for not that much money. If I don't want it I'd just order the cheapest most basic version of Windows I could, wipe it and move on.
I consider it highly anti-competitive to force people to buy an OS with their computer. It doesn't matter if you're a GNU/Linux person or simply already have a Windows license - it's forcing you to pay for something you don't want and don't need. And even if you want or need an OS with your computer (which many people, in fact, do), it should be an option[1], not forced upon you. As far as I'm concerned, this should be illegal by consumer protection laws.
In fact, there is a consumer protection directive in the EU that does just that - forbid unlawful bundling. It's just that no one knows and no one gives a shit, and here in Germany, there's a saying: "Wo kein Klaeger, da kein Richter." - "Where there's no complainant, there's no judge.". So, become a complainant. It's your good right, and those companies like Lenovo know it - that's why they make the process of getting a refund as arcane and customer-hostile as possible.[2] Most people will just bite it and silently pay the Windows tax, further fueling this vicious circle and the Microsoft monopoly.
[1]: For all I care OEMs can make it the default option, as long as I can choose "No OS" or "Preinstalled $distribution" - I don't care as long as I'm not forced to pay for something I ultimately won't use.
[2]: I had a slightly older (2008) mailing list post on (I think) Google Groups about refunds from Lenovo Germanu somewhere, but I seem to have lost the link. It included contact details for a guy at Lenovo Germany who apparently was responsible for granting refunds, but it took the author of the mail hours to get this information from the from the various hotlines.
A) You'll either pay the Microsoft tax or have Linux pre-installed, possibly both depending how how deep MS' hooks are.
B) Having all the drivers work is important, especially modern laptops will often switch their peripheral chips without changing even model # so there.