Upgrade to SQL Server 2012 and use columnstores. They thrive in these requirements. Seriously, download the evaluation editionevaluation edition and give it a try. Drop all indexes, drop the clustered index, simply add a non-clustered columnstore index on all columns and give it a whirl. I've seen cases just like your that reduced the execution time to 2-3 seconds, mostly because of segment elimination kicking in. Some supplemental reads:
- SQL Server Columnstore Performance Tuning
- SQL Server Columnstore Index FAQ
- Achieving Fast Parallel Columnstore Index Builds
- Work Around Performance Issues for Columnstores Related to Strings
- Use Outer Join with Columnstores and Still Get the Benefit of Batch Processing
- Using Statistics with Columnstore Indexes