Don't forget about the exchanges listed at https://kycnot.me/
There are a few that allow for cash <-> BTC exchanges.

As for the BATMs yes the fees are high but they are getting multiple whammies on expenses. They have to pay for the back end upkeep, they usually have to pay rest to the store they are in, they have to have customer support people 24/7 for the calls and so on. Those are all fixed, if they have 0 customers for a couple of days, the people still want to get paid, the stores still collect rent and so on. The KYC is independent of all of that.

-Dave