I think your assessment is correct. Have you tried this solution? The error doesn't quite match yours, but at least it's a client-side fix.
http://www.symantec.com/business/support/index?page=content&id=TECH47470
You should go through the Task Server and Notification Server KBs that you found, just to be safe, because it is possible that you have an issue on your NS. For example, let's say you provision 5 test systems, and 4 register successfully with the NS, then the NS stops processing NSE's in the queue. Your 5th test system is having trouble, so you conclude the unique log entries are client-related. (This exact scenario happened to me once.) Is the EvtQueue healthy on the NS?
I assume no proxy in your environment. I'll assume network configuration, VLAN, etc is similar between your problem client and the other systems.
Is the client on a slow link?