Why would the TrackedMessages_Copy_BizTalkMsgBoxDb SQL Agent job start failing with "Query processor could not produce a query plan"?
Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN. [SQLSTATE 42000] (Error 8622).
Our SQL guys are talking about amending the stored proc. but we've told them to treat BizTalk db's as a black box
Did you try updating the statistics on the database table referenced by the stored procedure (which is run by the SQL Server Agent job? The query planner uses those to decide how best to execute your SQL.