Query Performance depending on parameter 21seconds vs. > 14hours
I don't know about sqlserver but in an Oracle database, I would suggest making a trace of the sql execution, one that includes all waits and events that cause the query to spend time. This shows the exact circumstances where the sql is executing in and that might be very different than those in the environment where you did the explain plan. Sqlserver without doubt has a similar feature to show the real execution, including waits.

In Oracle we have sql plan stability. Maybe sqlserver has something similar? In that case, try to use that.