I'm having the same problem. I installed ZA Free for the first time on a brand new computer. The computer never had a previous version of ZA. The free product doesn't include the anti-spam feature, but I'm still getting the "restart Outlook to enable anti-spam" message when Outlook starts up after a reboot. I don't see the message if Outlook is restarted subsequently without rebooting.
I searched the registry for "SONICWALL" and found 2 entries, which I deleted. I found no entries for "mailfrontier".
I migrated to this computer using Laplink PCmover, and it may have it transferred ZA settings from an old computer. However, I've never had a paid version of ZA (or even a trial of a paid version as far as I can recall).
So, short of uninstalling and reinstalling ZA (and losing all of my settings), has anyone found a fix for this annoyance?