SQL Server index randomly performs poorly
I don't think this corruption. It sounds to me like out-of-date statistics are resulting in bad Execution Plans. When you rebuild the index the statistics are implicitly updated which is temporarily fixing your issue but not for the reason you think. You should have a strategy for updating Statistics (and re-organising/rebuilding indices). 

We use Ola Hallengen's index maintenance scripts.