To start:
Do I have to get a policy that says it is "HSA compatible" in order to contribute pretax (or have the employer do it) into my HSA savings acct?
Yes. There's more to an HSA compatible HDHP than simply the deductible amount. As you mention in your question, with an HSA compatible HDHP you pay all costs until you've met the deductible. Most non HSA compatible plans, even those with "high deductibles," offer first dollar coverage for a number of things which excludes those plans from qualifying for HSA contributions.
The issue is that before the ACA was passed "out of pocket maximum" didn't always mean "out of pocket maximum." A lot of times it was actually a "coinsurance maximum" but you would still owe copays. Or the "maximum" didn't include the deductible, or drugs accrued to a separate maximum etc.
Generally speaking, pre-ACA plans actually had much higher maximum out of pocket limits than many people realized.
Now, post-ACA, there is a legally mandated maximum "out of pocket maximum" that includes all covered dollars you pay and that applies to HSA compatible HDHPs just the same as to a vanilla PPOs. The issue is population level average claims. The difference in cost to the insurer is virtually indiscernible between a HSA Compatible HDHP with a $3,000 deductible and a Platinum PPO with $0 deductible because if you're really in trouble you're going to hit the out of pocket max anyway and cost many times that number. The difference between $5,000 and $2,000 (or whatever) of deductible when you're dealing with a $400,000 claim is meaningless and it is the big claim sick people that primarily contribute to total claims and drive medical costs.
Finally, and cynically, these are products. Products are priced to the market. Simply adding up total premium and total expected medical costs of a PPO and an HSA-HDHP doesn't factor in the tax savings of the HSA and is thus not an apples to apples comparison. It's possible that HSA premiums price some amount of your expected tax savings because the market for HSA compatible HDHPs will bear it.
In the end carriers aren't saving much of anything when you compare the overall claims cost of an HDHP vs any other health plan (considering the same networks and other variables).