Nick,
It's simple, play by their rules ...
Stop by that bank, put $100 in and 'open an account', deposit the check (making sure it is good first), then withdraw the amount of that check, then withdraw the rest of you money and close your account.
I really suspect that, if you explain that to the bank, the bank will say 'To h$ll with rules and regulations, *it will cost us less* if we just cash the check' - providing that the check is good.