Are the SCSI id's the same since the controller was replaced?
Are the Backup To Disc folders online and working? And can you backup anything to them using, say, a brand new test job?
What does the eventlog say about the bengine.exe errors?
The 4 technotes you mention deal with troubleshooting tape drives, but you mention the MSA is failing? Are the failing jobs running to the MSA or MSL?
If the MSL has the hardware errors, did you perform Step #4 from http://support.veritas.com/docs/255501 ? It so, did you see any noticible errors in the hardware trace? For more information on tracer see http://support.veritas.com/docs/285630
If it is the MSA that is reporting the 'device is offline,' have you checked to see if you are getting any errors in the event logs regard write failures or timeouts when writing to the disks? If the MSA is attached locally to the Media Server, have you tried enabling write back caching on the disks?
Can you try to backup to a volume other than this MSA to see if the problem is with this device or not?
Do all of the jobs also fail at the same 45 GB mark every time?
Also, make sure that the Backup Exec services as well as System Logon Account are all set to use a full administrator account.