Now that this has made it through testing and pushed out to production I'll give you the results. Adding the LOOP join hint to each of the RIGHT JOINS along with declaring local variables within the STP and setting them to passed in values did the trick. The query is now consistently completing in fractions of a second with the occasional 3-4 second execution. Far better than the timeouts we were seeing on the server. I also removed the indexes that were recommended by the tuning advisor on both the test and live servers. This did not appear to affect performance though it did make me feel much better about it.
Thanks again everyone for your assistance on this one!
Jack