Was it in a "RUNNABLE" or "RUNNING" state or both. The estimated rows does look odd. It's a little hard to say for certain without looking at the plan what might have happened. I would have guessed parameter sniffing, stale stats, of something along those lines, but you said there's no parameters and you update stats regularly.
You do have one option to make sure the speedy plan always gets taken. You can use sp_create_plan_guide_from_handle to pin the plan in the cache. You'll need to get the plan_handle during the next run. The plan will have to be in the cache when you do this. All this does under the covers is create an XML plan guide.
thanks for your response. To be precise, statuses were a bit confusing: query status was "running" in sys.sysprocesses and "runnable" in sys.dm_exec_requests.
Thanks for your tip about sp_create_plan_guide_from_handle. I will look into it.