When a previously-fast SQL query starts running slow, where do I look to find the source of the issue?
When a query that used to run fast suddenly starts running slowly in the middle of the night and nothing else is affected except for this one query, how do I troubleshoot it...?


You can start by checking if the execution plan is still in the cache. Check sys.dm_exec_query_stats, sys.dm_exec_procedure_stats and sys.dm_exec_cached_plans. If the bad execution plan is still cached you can analyze it, and you can also check the execution stats. The execution stats will contain information as logical reads, CPU time and execution time. These can give strong indications what the problem is (eg. large scan vs. blocking). See Identifying problem queries for an explanation how to interpret the data.


  Also, this is not a problem with parameter sniffing. I've seen that before, and this is not it, since even when I hard-code the varaibles in SSMS, I still get slow performance.


I'm not convinced. Hard-coding variables in SSMS does not prove that the past bad execution plan was not compiled against a skewed input. Please read Parameter Sniffing, Embedding, and the RECOMPILE Options for a very good article on the topic. Slow in the Application, Fast in SSMS? Understanding Performance Mysteries
is another excellent reference. 


  I've concluded (perhaps incorrectly) from these little experiments that the reason for the slow-down is due to how SQL's cached execution plan is set up -- when the query is a little different, it has to create a new execution plan.


This can be easily tested. SET STATISTICS TIME ON will show you the compile vs. execution time. SQL Server:Statistics performance counters will also reveal whether compilation is an issue (frankly, I find it unlikely).

However, there is something similar that you may hit: the query grant gate. Read Understanding SQL server memory grant for details. If your query requests a large grant at a moment no memory is available, it will have to wait, and it will all look as 'slow execution' to the application. Analyzing wait info stats will reveal if this is the case.

For a more general discussion about what to measure and what to look for, see How to analyse SQL Server performance