I'm not saying I necessarily agree with what the two bank are doing, but I wanted to share their reasons.
However, they've taken the stance that they're not dishonoring the check, they're refusing the transaction for a non-customer. When the non-customer approaches a teller and hands over the check and says "I want to cash this", the first question is "Do you have an account with us?" and if the answer is "No", the teller doesn't even go through the steps to verify the check or see if the funds are there. So it's not like the check goes through the process and is found to be good and is then rejected. The moment the person indicates they are not a customer, they are told the bank is unable to provide services for non-customers. Obviously, people yell and scream.
However, this has been in effect for quite some time and it's no longer a big issue.
Also, before this policy went into effect, the following steps were taken (at the smaller community bank):
1. Advance notice of 60 days was given - displayed in the branches, letters sent to business customers who issue payroll checks, etc.
2. Change was made to the account agreements to accomodate the wording that the bank reserves the right to deny check cashing transactions to non-customers when they present the check over the counter.
3. Frequent cashers (such as the payroll check recipients) were notified and reminded during the 60 days. Many ended up establishing some sort of relationship with the bank, whether it was opening an account, safe deposit box, etc.