Query runs fast but occasionally never completes
It looks like the statistics are off. From the plan you posted it's estimating that it's going to read 64,000 rows, but it's actually reading zero. That's a very wide disparity. I'd suggest a few things. First, update the statistics with a full scan. Any index rebuilds ought to have taken care of that, but with this disparity I'm wondering if something is up there. Next, make sure that the constraints are all in place (although, this plan isn't referencing constraints since it's a straight index seek with a TOP operation). Finally, capture the wait statistics for the system to see what's actually causing things to run slowly. You can use extended events to capture the wait metrics for just this query, so that's an even better approach. Also, a 64,000 row range scan from a seek is a little excessive unless you have millions of rows. However, this could still be a part of the statistics being off.