What a great article! It shows the incredible thought process and the tenacity a true professional has in the world of SQL Server. Nice job and congrats on your success!

As a bit of sidebar, was this an all-in-one query? If it was, I've had a great deal of success using the "Divide'n'Conquer" method of dividing the problem up using a Temp Table here and there to hold smaller interim results and then join to those. It's a way of doing a manual and guaranteed "force order". The advantage there is for future troubleshooting because you can execute and measure one section of the code at a time for tuning purposes. It's not often that a simple hint such as FORCE ORDER will actually solve the problem either initially or permanently simply because "things change".

That, notwithstanding in this case, very nice article. It should be required reading for anyone who says, "Well, of course it's slow. There's a lot of data." and then walks away from the problem (which I've seen happen way too many times).