UPDATE: For anyone that may encounter a similar issue.

I've dug a bit deeper, and I think what is happening is that sometimes the generated query plan undergoes partition elimination at compile time versus at runtime. When at runtime, I have verified that the number of executions is zero for tables with check constraints outside my range.

I still don't quite understand why the non-clustered index is sometimes ignored when it should be covering, but I have had the most luck with the FORCESEEK query hint.