Thanks for the responses everyone :).
@sachin; you are right I named that strangely. It should be called, AvgbyYearbyAccount. I called it this because the account is the most granular level in the aggregation and it is averaging it across years of data.
@jeff; thank you for all the detailed information! In the final queries there are quite a lot of filters so it does execute fairly well (About 10 minutes across 100 million rows so not too bad).
I have actually done massive partitioning schemes before and it was anything but easy! However, now that you bring that up, it was pretty much a custom developed solution I built, so I am wondering what you have as far as the partitioning goes.
Also, that is really good information in regards to the indexes, I did not know some of that. I am going to have to go back and check the execution plan and see what it is doing now and see if I can tweak the indexes to make it go faster ;).
Link to my blog http://notyelf.com/