Auto update only kicks in after 20% of the table has changed. On larger tables that's no where near sufficient. There have been traceflags added to SQL 2008 to adjust the threshold but they're not back-ported into SQL 2005.
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