I do think there are legal concerns that need to be addressed if you are going to do this. First, you probably want your account agreement to include the depositor's permission for the bank to charge such a fee. There is always the possiblity that (without such a clause) your depositor will make a claim against the bank for wrongful dishonor because the bank refused to pay a check unless the payee paid the fee.
Also, if you are charging to cash payroll checks, you may be creating a problem for your business depositors. Some states have rules requiring employers to pay employees with checks that can be cashed "at par" or at face value at a local financial institution. If you charge a fee, the employer may be subject to claims by their employees for violating this requirement. I believe that Bank of America or Wells Fargo just got sued for something like this in (of course) California.
_________________________
Nobody's perfect, not even a perfect stranger.