I used to get those messages.
Assuming your backup runs when nobody is around, have your users log out of Outlook when they leave.
I have a little scheduled job on the backup server that will force Outlook to close on certain PCs whose users are forgetful.
In \system32 (Win2003) you have a nice little utility called taskkill.exe.
taskkill /f /s COMPUTERNAME /im outlook.exe
It leaves the PC running, just forces OL to close. (If you decide to take this drastic measure, let them know this will be happening!)