Might have been a bad plan in cache on the day it was running bad and that plan got flushed out and a correct plan was created the next day.

you can use this to check the cached plans for the proc and how often that plan has been used.

SELECT UseCounts,RefCounts, Cacheobjtype, Objtype,

dbid AS DatabaseName, text AS SQL

FROM sys.dm_exec_cached_plans

CROSS APPLY sys.dm_exec_sql_text(plan_handle)

where text like '%<proc name>%'

ORDER BY usecounts DESC;