Is there a way to write a script at the Outlook client that will make sure the message size—including an attachment—doesn’t exceed our limit as soon as the message composition is started?
Yes, you can do that with VB by using the ItemSend event like this:
Private Sub Application_ItemSend(ByVal Item
As_ Object, Cancel As Boolean) Item.Save If Item.Size
This uses the item.size property to determine the size of the message item (attachment and all) and compares it to an arbitrary value (in bytes). In this case, I've set the checkpoint to be 100,000 bytes (roughly 100K) but you could set it anywhere you like. It then displays a message box showing the user the message's size (in bytes) and letting them know it's too large. It then cancels their send, leaving the compose message screen up for them to modify their message.
If their message is under that size value, the message will be sent with no interaction with the user at all.
Note that you do need the item.save method before the item.size, because before the item is saved the size will always equal zero so your comparison always will fail and every message will be sent.
To distribute that to your users I'd compile it into a COM Add-in and distribute that—but you could just distribute the VBA project as well (if your users don't have any preexisting customizations that would be overwritten by this new project).