Answer:
If, as you said, the check appeared on "stop suspects" report when it was posted, the paying bank had an opportunity to compare its stop payment records and the check image (assuming they were able to pull up an image) to verify the stop applied to the check, and timely return it unpaid.
I suggest that's a good argument for not honoring the paying bank's request or its claim against your bank's encoding warranty, whichever they submitted