A bank can decide whether or not to cash checks for non-depositors, but runs the risk on payroll accounts of constantly having to do so. Dana is correct that positive pay is almost the best way to go, but for thousands of businesses, who have only a few employees, it really is not feasible to do so.
If I write a check on my bank and give it to my employee, who takes it to my bank to cash, but is not a depositor there, the bank can refuse to cash it UNLESS THE EMPLOYEE IS PROPERLY IDENTIFIED. Therein lies the rub. What is the real meaning of "properly identified"? It means properly identified by my bank, in this case. If the bank is not satisfied, it can refuse to pay the check.
My agreement with the bank says that when a check is presented that is properly payable, they must honor it. If all else is in order, date, signature, etc., that "properly identified" takes on the balance of the properly payable requirement. If the person IS properly identified according to my bank's definition, and they STILL refuse to pay it, they can be liable to a law suit from me ... but not from the payee on the check.
It is not uncommon for payroll checks to be fraudulently copied and presented for payment. I'm sure some banks feel that by charging for the encashment of payroll checks, they can help recover some of the losses they suffer through improper payment. But then the bank has turned into a check-casher.
This is not a problem that is going to go away. Sometimes a targeted effort on the parts of new accounts people can turn some of those payroll customers in depositors. That helps the most.