The latest update for BE 16 is BE 16 FP1 (which includea the Hotfix you mention)
As such if you are patching servers I would suggest you use the latest update - note as per our current release policies, FP1 is not yet on Live Update so has to be manually downloaded and applied from the following technote
http://www.veritas.com/docs/000116034
With regards the reboot requirement
1) As per pkh comment we cannot say in advance if a given installation will require a reboot as the state of other installed software and other operating system components at the time you install the patch may make a difference. Usually Backup Exec will not let you open the Admin console on the server (after istalling an update) if this happens and a reboot is still needed.
2) if it does not need a reboot and then 6 months later, after mutliple updates to different applications and the OS itself, you reboot and the server does not come back up properly, how do you know which change you made during the 6 months caused your problem (so troubleshooting is harder) - recommended pratice (really for any software not just Backup Exec) is therefore to plan to reboot at earliest opportunity, just for piece of mind
Note: really the above is about the BE server itself, we do try to reduce the requirement for rebooting systems with only our remote agents installed - however the drivers used by Client Side Deduplciation and/or GRT processing do sometimes end up in a state where a reboot is required,
