It does indeed happen when an account isn't close to zero. And I always disable "overdraft protection" on my accounts - no, if I don't have the money, I don't want to pay you $35 for the privilege of "avoiding embarrassment" at the point of sale. Apparently, depending on authorized (but not yet settled) debit transactions (of which there can be multiple for the same event), the time of day, how long it's been between those authorizations and settlement, and some hand-wavy heuristic that no one can ever explain, this particular account would incur the fee for no reason the humans at the bank could explain.
And they always start off with the "be more responsible" spiel, until I get them to do the math themselves. Then they look confused, reverse the fee, and promptly forget about it. Until it happens again.
Part of the problem in these cases is factoring in those non-settled charges - money doesn't actually move until the settlement comes through. Sure, auths should affect available balance (and then refuse to accept more transactions if there's not enough available), but shouldn't be affecting the balance calculation for NSF fees.