How do the backup solutions of Veeam and Veritas compare?

If you have a fully virtualized environment Veeam is easier to use.

But if you don't have a virtual system (e.g., you have a NAS server or a non-virtual server), probably bkupExec is better.

As mentioned by many Veaam is best suitable for virtualized environments. 

As to Veritas, it has 2 products: Backup Exec and NetBackup. 

Veritas NetBackup is more suitable for Heterogenous OS and Database environments. 

Veritas Backup Exec is suitable for SMB and mid-sized companies. It supports virtualized environments, file and database-level backups (Microsoft-related DB) and is cost effective.

Veeam is best for Hyper-V & VMWare replications snapshots, HA failover. 

Live backup is available in VMWare only.

Veritas - it specializes in storage management software including the first commercial journaling file system, VxFS, VxVM, VCS, the personal/small office backup software Backup Exec and the enterprise backup software, NetBackup. 

Veritas Record Now was an early CD recording software.

If you need more app and DB backups integration, it's better to use Veritas. 

For VMS with MS apps only, I choose Veeam. Veeam is a great software for virtual environments but needs to make better integration with larger apps and DB cause of the consistency you need to guarantee.