Are you sure that updating stats with fullscan doesn't help? Changes in estimated rows before/after is usually indicative of statistics-related problem (or bad parameter sniffing).
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability