Mmm...what are the hardware specs of that server, and what else is it running besides Backup Exec 12.x?
My suggestion Markus, would be to run Perfmon on that server and see where you have your resources being leached. You can also check in Task Manager and see what your memory and CPU utilisation is for all the BE services.
Also try eliminating things like virus scans running at the same time, application maintenance etc.
Has it just cropped up, or has it been ongoing?