Quite a lot of banks will simply say "no,
    not with any amount of paperwork"

You're going to need to provide a source for this statement. HSBC was just pilloried in the press for denying large withdrawals to the point that they reversed their policy.

"Suspicious Transaction Reports" or "Currency Transaction Reports" only take a few minutes at most and can be completed online. The AML threshold applies whether you're using cash or a check, so you're basically saying that banks won't deal with transactions over $10,000 which is absurd.

Nearly every bank and credit union has a 'Large Cash Withdrawal' policy that merely requires ~7 days' notice prior to the withdrawal so that they can order the cash. It also of course waives their liability if you lose that cash or get robbed, but that's to be expected.