Another note on getting the error: “The message was not found in the Message Box or the Tracking databases. This may be caused by one of the following conditions: (1) message tracking is not enabled; (2) the message(s) is no longer referenced by a running or suspended service instance; (3) the Message Box tracking tables have been automatically purged; or (4) the SQL Server agent is not running on the Message Box servers.”
Make sure whoever sets up the SQL Server Agents does it under the service account intended for that and not their own login!