1. Yes, you can have them installed. But stop the legato services, otherwise BE might have issues with device connectivity.
2. Yes, old tapes of legato can be used with Backup Exec, but data may not be restorable at times. You may try catalog though, but cannot assure if that would work, as legato is not in the list of softwares that are supported for restores using Backup Exec. But, new backups to same tapes should work without issues, but it would overwrite the tapes.
3. From the requirements, these are the licenses i would suggest:
1 Backup Exec core license
2 Exchange Agent license, for mailbox recovery
6 remote agent licenses, assuming you will be installing Backup Exec on one of these servers mentioned in the list.
ANd 1 Active Directory Recovery agent, if you would like to have individiual active directory objects restore feature available.
I hope this answers your questions. If it does, mark it a solution.
These are the ones you should be looking at in the symantec store:
Symantec Backup Exec™ 12.5 for Windows Servers
Backup Exec 12.5 Agent for Microsoft Exchange Server
Backup Exec 12.5 Agent for Windows Systems
Refer following url for information on contactig Sales:
Please mark it a solution, if this is useful.