Checks drawn on a Canadian Bank without a US routing in the MICR line will not process and must be sent as a collection item. Some may have a payable through routing number and paid in the US. This is more of a draft than a check, and its still good practice to send as a collection item.
If you have sent a check that will not route in your normal transit, its possible that the Fed debited the banks account and returned the item (or lost it) in such a manner that operations personel may not have known what to do with it. Have you checked the Suspense Account lately.