You might not want to go down that road, and I don't blame you, but you might have to. Are you doing full scans on the statistics or just using the default sampling? A full scan might make a difference.

Just so you know, we have a couple of tables that we update statistics on several times a day. Partly this is because of bad design that we're not allowed to "fix" because it's a financial system and they'd would have to go through a ninety day test cycle. Partly it's because the data is just volatile enough and just odd enough, that it needs VERY good statistics. Most of the rest of our databases run just fine with statistics updated weekly.

Also, have you checked the index fragmentation levels?