Next time the query misbehaves, can you capture the actual execution plan (not estimated please) before and after the index rebuild? Without that, just guessing.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability