It is unlikely that anyone will run into the same issue I have been facing over the past few days, but I figured I should post my eventual solution to this nightmare.
The starting symptoms of the issue I had were that the backup exec agent would not start... the service would sit at starting for a minute or two, then fail saying that the service did not respond in a timely fashion... or some generic message like that. Pushing out the remote agents again, trying different versions, manually cleaning the registry... none of it worked.
The problem started with the Mariofev virus that was discovered on almost all the workstations and servers at this site. The behavior of the virus is to copy itself to any network shares that it can access, then create an autorun.inf file in the directory such that every time a user opens that directory the virus autoruns and copies itself into the unknowing users registry. The virus then appends itself to any executables it can reach in a manner of ways, including attaching itself to outgoing emails. With some virus updates and installations of Spybot, the worst of the active virus was caught and stopped from further spread.
In addition, a Trojan W32.AgentMon found its way onto several systems, particularly the ones having problems with the backup agent. The action of this Trojan is unknown, but it modifies the tcp stack with some sort of hook. This was overlooked by all the antivirus and antispyware systems installed. It was discovered that a single file named vapor.dll exists in the C:\windows\system32 directory of infected computers with a date/time stamp of the moment the Trojan activated. This dll deeply entwines itself with the winsock/tcp functions of windows causing havoc due to being poorly written (I am not sure that it actually functions, but it messes stuff up).
While working with Symantec support on the backup agent installation issues, I decided to grab a copy of process monitor from sysinternals and track all calls etc from beremote.exe (the backup exec remote agent)… and low-and-behold when beremote.exe (and soon come to find any network application) tried to establish a port it was directed to call vapor.dll first… which promptly crashed. I renamed vapor.dll to vapor.dll.old and suddenly no dns worked. Returning the file to its original name re-enabled dns. It was clear at this point that the tcp stack had been hijacked. I began thinking that it may be a good idea to try and rebuild tcp/ip on the servers to see if that fixes the issue.
Following MS article 811259, I rebuilt Winsock and reinstalled tcp/ip on the network connection, rebooting after each. After rebooting, beremote.exe started up just fine and the system could get out to the internet while vapor.dll was still renamed. Examining process monitor, no calls are made to vapor.dll anymore.
I was then able to push out the backup exec 12 agent via the normal method and start the backups running. Backup of the two systems is being performed as I write this.