The easiest way to fix this is to change the settings on the user. One or two solid whacks to the user's left hand with a hammer (or similar object) is an effective way to get them to use their mouse as a righty.
If that doesn't work for you for some reason, the second easiest way I've found is to give the user access to a limited control panel on the server where they can reverse their mouse settings themselves. (At least as of Windows 2003, this was a per-user setting, so it won't impact everyone who uses the server.)
You can do this via GPO, and will be found under User Configuration -> Administrative templates -> Control Panel -> "Show only specified Control Panel applets" -> mouse.cpl
You can also solve the problem with roaming profiles fairly trivially, but I figure you don't use those, or you'd have fixed it already. Roaming profiles are still more of a pain than they're worth anyway. :(