Why doesn't this udev rule trigger upon removal of the device?

Alternative solution

After finishing writing the answer bellow, I realized that what you're trying to achieve could be accomplished much more elegantly with the help of xinput or even using Xorg's config. Make sure to read the documentation about controlling input devices in Xorg.

Using udev (an answer to your question)

According to my tests there are two problems with your rules:

1. At least on my Ubuntu GNU/Linux 12.04, no checks for ENV{DEVTYPE} ever match (even though it is reported properly by udevadm info and udevadm monitor). This is the reason you don't even see the add rule matching.
2. You should remove the OWNER assignment from the remove rule. It doesn't make sense and udev ignores the rule altogether.

Please try with the following two rules and see if they solve the problem.

ACTION=="add", ENV{ID_MODEL}=="USB_Receiver", ENV{ID_VENDOR_ID}=="046d", ENV{ID_MODEL_ID}=="c51a", RUN+="/home/user/.scripts/Troubleshooting/Bugfixes/mouseswitcher_wrapper 1", OWNER="user"
ACTION=="remove", ENV{ID_MODEL}=="USB_Receiver", ENV{ID_VENDOR_ID}=="046d", ENV{ID_MODEL_ID}=="c51a", RUN+="/home/user/.scripts/Troubleshooting/Bugfixes/mouseswitcher_wrapper 0"

Additional considerations

Several things to consider:

1. it's much cleaner to use ATTR{idVendor} and ATTR{idProduct} for classification of the devices. You can safely change the add rule to use them, instead of ENV, but I left them like this for the sake of simplicity. Currently add and remove rules are almost identical.
2. Consider the security implications of running a script as root in a directory that is writable by other users. In your particular case, it's not a serious issue, but I wouldn't call it a good security practice. IMO it would be much better putting the script in /usr/local/bin/, making it owned by root.root and mode 0755.
3. Make sure that you want the mouse device to be owned by your user, there is really no need for that, PolicyKit and Xorg should be able to handle root-owned devices without any problems.

If you don't need to change the owner of the device and your setup works with a root-owned device, then you could simplify your two udev rules to this one:

ACTION=="add|remove", ENV{ID_MODEL}=="USB_Receiver", ENV{ID_VENDOR_ID}=="046d", ENV{ID_MODEL_ID}=="c51a", RUN+="/home/user/.scripts/Troubleshooting/Bugfixes/mouseswitcher_wrapper $env{ACTION}"

This will call your script with the corresponding action - remove or add, so you will need to modify your script to handle these arguments.

To prevent the rule to match (and the script to run) more than once you need to make the rule more specific: the rule matches for each "input" (buttons, etc) of the mouse. That's why it's executed repeatedly. Try adding ENV{ID_TYPE}!="hid" or ENV{ID_USB_DRIVER}!="*hid*" and see if it works as there is only one device that is not HID - the top usb_device.

PS: If you want to make your mouseswitcher script more flexible, and are running a system with ConsoleKit, you could use ck-list-sessions to get the user that is currently logged in and use that info for setting the XAUTHORITY variable.

It's been a few years since the previous answer was written. It appears that since then udev has changed so that the udev solution no longer works, at least for Ubuntu 18.04 with udev package version 237-3ubuntu10.29. I'm posting this answer for the benefit of people encountering this problem in the future, since I haven't found any other reports of this issue.

With this version of udev, ENV{ID_VENDOR_ID} ENV{ID_MODEL_ID} are not set for remove events, so rules will never match on these variables. A workaround is to use ENV{PRODUCT}, which is set for both add and remove events. ENV{PRODUCT} has the form idVendor/idProduct/bcdDevice, so it can be matched with a rule containing:

ENV{PRODUCT}=="xxxx/yyyy*"

where xxxx is the vendor id and yyyy is product id of your device.

A side note, compared to the time of the previous answer, is that udev does now set ENV{DEVTYPE} correctly and it can be matched in rules.