Okay, I figured out the problem.
First, I got a couple of things wrong. My engineering team took BOTH the old primary and the old secondary machine down. The secondary machine was being used as a secondary machine in the test environment to test fail-over procedures. So the real situation was I had a primary and a witness that had lost the secondary machine.
The solution to stop the flood of alert message was a bit involved. I tried using the GUI to remove log shipping, but that failed since it could not talk to the secondary server. Ultimately, I had to do some behind the curtains work.
First, on the primary I had to run the following script for EACH database that had been log shipped.:
@primary_database = LogShipDB, -- sysname
@secondary_server = SecondaryServer, -- sysname
@secondary_database = LogShipDB -- sysname*/
@database = LogShipDB, -- sysname
@ignoreremotemonitor = NULL -- bit
After this I had to run this command on the Witness machine. This was a bit scary as I was going straight after systems tables without using the GUI or any stored procedures.
delete FROM log_shipping_monitor_secondary
WHERE secondary_server = 'vmaxBirmSQL1'
Note that on the Primary machine, the queries had to be run from the master database but on the Witness they had to be run from msdb.
Yuck. What a mess. Glad I got it figured out.