The following has instructions for troubleshooting both Internet Explorer and Firefox.
"Hyperlinks don't work in email":http://www.the-pc-guru.com/Hyperlinks_dont_work_in_ema.php
The instructions above are a bit more detailed than Microsoft's, but I did notice that the Microsoft article has one last step in "Method 2":
8. Save these settings, and then repeat the process for other URL protocol file types.
There are several "URL:..." file types in the Folder Options list. Among them are "URL:HyperText Transfer Protocol" and "URL:HyperText Transfer Protocol with Privacy". You mention that some types of links do work and some don't. Maybe the FedEx and UPS tracking links (the ones that do work) are using the "Privacy" (secure?) protocol, while the links that don't work are using the standard protocol. You may need to verify the file type associations for more than one "URL:..." file type.