At work we had an issue where our sql performance (SQL Server 2005) was very slow – much slower than we needed and everything looked OK but in the production environment (to which we don't have access – rightfully) things were not ticking as they should be. We had a requirement to be able to process ~200K / hour and we were barely managing ~ 44K / day! Ouch!
As it turns out, the solution in the end after a lot of digging and flapping around was changing the type of one of the columns which was defined as a nvarchar(MAX) to a nvarchar(400). The data we were storing in this column can easily fit within 400 characters and we don't need the MAX. The reason this helped is because a MAX is not indexable. The database was flagging this as warning but this was missed. Changing this increased our perf. from the measly 44K records being processed in 24 hours to processing 410.0K records in 16 minutes! Sweet!
So the lesson is, if you got a MAX column it cannot be indexable.