Looks like order IDs created via the Connect API share address space with those created via WebCollect:
This issue is related to the default dynamic ORDERID ranges '4xxxxxxxxx' or '7xxxxxxxxx' which is used by Connect API. Since your system is processing through two different platforms (Legacy and Connect) where the legacy integration still provides its own ORDERID, it would cause issue if Connect use an ORDERID which was removed from the legacy system. To avoid this from happening again, would it be feasible to update the legacy integration to not use ORDERID that starts with '4' or '7'? That way the ORDERIDs from two platforms will never collide. Another option is to not include ORDERID in the legacy API.
It would be a big change to not include the ORDERID, but should be pretty simple to skip the 4xxxxxxxxx and 7xxxxxxxxx ranges.