If a product simply requires a replacement of the .EXE file, what would be the expected way to deliver this update to multiple workstations in a large enterprise?
Is an .MSP file preferred?
Or should a new .MSI file be provided and it simply be treated like a new version of the product?
Depends a LOT on how big the software is.
It if is small enough just make an update MSI.
If the package is HUGE, then an msp may be better.
Read the documentation how versioning is supposed to work. THis COULD be a minor upgrade or not, depending on your policies. I would put it in as minor upgrade.