Timeouts are caught, and we're not getting any of those. Tracing isn't recording any errors or warnings, so as far as we can tell, the Delete is being done, it's not timing out, but it just isn't deleting the rows. it's not a collation issue nor is it any odd chars in the data, they're just numers.
The only oddity we've found out is that they're running the 2005 DB in 2000 compatibility mode.
We don't have any access to the server, we can only ask them to do things for us.