I had the same problem w/ a piece of software where I work...and I took work at a financial institution. And I can tell you this: there's no way this app will "only" run as a domain admin. Try this:
- If it's win2k/xp...change the security template to "compatible". This will ease the program restrictions a bit while still keeping security.
- Make the user of that workstation a power user and try it out if just the above doesn't work. If that fails, make them a local admin & train them about installing apps & such on this machine.
- Look at what files on the network this app needs access to and give appropriate access.

Like I said, there's no need for this, and I've dealt w/ this and fixed it. The person who set it up in my case (before I worked there) was just too lazy to figure it out. I've since changed it and it worked w/o issue.

Regarding someone saying Backup Exec needs Domain Admin rights: BE doesn't need to be a domain admin either...and by having the account that uses BE as a domain admin, you're leaving a huge security gap wide open. Just give the account it uses the appropriate permissions to the directories it needs to backup. Yes, it'll take a little time but it's a much more secure way of doing it. I fixed this issue as well when I started working where I do. Just make sure you understand file permissions, and you'll be all set.

Good luck.