A methodology for tracing a query that sporadically runs for hours instead of seconds
Based on your thorough outline, I believe you may be experiencing a problem with your table statistics. 

Tables only automatically update their statistics when certain thresholds of row updates are passed, in the case of any table over 500 rows it requires 500+20% of the rows to change. For example your million row table requires 200,500 row changes before it will update statistics. 

An index REBUILD will update the statistics on a table (REORGANIZE does not).

I think your tables are growing over time and eventually invalidating your statistics, but not enough to trigger an automatic update. However, your reindexing job is not triggering an actual REBUILD for the relevant tables until after your query starts performing poorly due to the last couple changes from earlier in the day. If your changes are inconsistent and small enough increments this would make the performance degradation consistent and sudden. Your reindexing job then fixes the problem after the query has ran poorly and everything looks fine the next morning.

Things to check to confirm: 


If you can catch a 'bad' query plan check the pipes' Actual versus Estimated number of rows returned. If this is radically different it's red flag for statistics issues.
Check the criteria on your Reindex Job to confirm that it's not updating the indexes on the query's tables regularly.
If you can use the following query regularly you can track when the statistics are updated: 

SELECT name AS index_name
   ,STATS_DATE(OBJECT_ID, index_id) AS StatsUpdated
FROM sys.indexes
WHERE OBJECT_ID = OBJECT_ID('SchemaName.TableName')
 


If you are running SQL Server 2008 R2 Service Pack 1 or later, you have the option to enable documented trace flag 2371 to dynamically update statistics more frequently:


  The higher the number of rows in a table, the lower the threshold will become to trigger an update of the statistics. For example, if the trace flag is activated, update statistics will be triggered on a table with 1 billion rows when 1 million changes occur. If the trace flag is not activated, then the same table with 1 billion records would need 200 million changes before an update statistics is triggered.


The new behaviour is enabled by default (i.e. without the trace flag) from SQL Server 2016 onward, for databases at compatibility level >= 130.