It could be the check itself or the type of account they are using, etc.

You may find you have the issue with other banks if they use similar systems to try to reduce check fraud.

I assume the message is something along the lines of "we have private info suggesting this check might not clear"