Scripting

What OS do the target machines have? If they're Windows 7 or above, you could do something with Powershell/Windows Forms.

A previous poster found and used an HTA but many shops disable HTA execution.

As you can tell, there's nothing native in Windows Installer that will help here.

The other point to bear in mind is that many shops deploy everything silently so pop-ups of this kind will, unless expertly coded, make the deployment hang, as the deployment would be carried out using the local System account which, as you know, has no console on which to display windows for messages, etc.

At most clients I've worked at, a round-robin email would be sent, detailing that some update is due to be deployed on date 'x' at time 'y', that users need to log off from machines and that, if they don't log off and consequently lose data, no-one will care!. Normally, a reminder is sent the day before the actual deployment and then a final an hour or so before. If, however, your client wants to pay for development of a robust messaging system as an alternative, I'd bite their hand off and invoice accordingly.

Lastly, please remove your duplicate post.