Good Vs Bad Query Plan - only DBCC FREEPROCCACHE was able to resolve the issue

Hi,
We have two query plans for the same "prepared SQL statement", one runs slower and one runs faster. The on runs slower does SORT operation which takes more CPU resources and has StatementOptmEarlyAbortReason="GoodEnoughPlanFound", the other one (Good one) doesn't do any sort, no CPU usage, but has StatementOptmEarlyAbortReason="TimeOut".
The slow query plan was created all of a sudden one day after a manual update statistics job ran (sp_updatestats with default values) , the only way we were able to resolve this issue is by running DBCC FREEPROCCACHE. After running this, a new query plan created for and that works fine.
I can post the both XML plans if anyone wants to have at look at them.
Do you think running UPDATE STATS with FULLSCAN on a weekly basis is needed?
I would also like to find out the differenence, betweent these two statements in XML execution plan
StatementOptmEarlyAbortReason="GoodEnoughPlanFound" Vs StatementOptmEarlyAbortReason="TimeOut"
Thanks
Dev

May be your default sample size (10%) is not good enough.. how big is your table and what is the workload like - do you have lot of inserts/deletes happening on a daily basis? you could modify your steps to do a full scan just for this table..

That is the biggest table we have 57GB in size, have 230 million rows of data (after the archival), for the current period. Yes, we do have lot of inserts and bulk deletes happens once in a month when we run the archival process.
If we need to run FULLSCAN, we can only on a week end, that too, if that doesn't lock the table. We can't afford to have locking on this table. We are working setting federated databases and split the table, but that will happen only Dec 09.
Thanks
Dev

Ad suggested by dinkar...can you reindex the clustered index of this table with a fill factor around 75% and monitor the changes. Apart from this if possible can you post the table schema.