If the payroll check is also drawn on your bank, you have a contractual obligation to your business customer to negotiate the check. If the check is not drawn on your bank, you are not obligated to cash it, take it for deposit or do anything at all with it.
You may request that the customer deposit the check subject to any Reg CC holds you choose to place. The customer has the right to say, "No" and take the check with them.
I can't possibly opine on how a teller processes a check deposit with no cash back on your system.