They can’t refuse if it comes through normal collection channels (assuming that the check is otherwise good).
For example, if you have a check written on an account at Bank A and you deposit in your account at Bank B, it will be sent to some sort of clearinghouse in the federal banking system, and eventually be presented to Bank A a day or two later.
The difference between presenting a check through the clearinghouse system and presenting it at the window is that there are better defenses to fraud in the normal collection system. For one thing, there is a delay in payment. If the payee on the check sets up a new account, the delay will probably be even longer. If the circumstances are suspicious, the funds can also be put on hold. Also, when you set up a new account, they check you with CHEX systems.
It’s a controversial issue, since it’s arguably an impairment of the payee’s rights under the UCC. Not only that, but consider this scenario:
You are a tradesman with a customer who is a bit of a deadbeat. Finally, the customer sends you a check for $500 written on his account at Citibank. If you deposit that check in your account at Chase and it bounces, then you will be hit with a $10 or $20 fee. So it seems attractive to simply present the check at the teller window at Citibank. That way, if the check is no good, they can’t charge you a fee.
Some banks will let you do this, particularly if the dollar amount of the check is under some threshhold.