Is it ok to increase `innodb_stats_sample_pages` up to large number?
Changes to the statistics has plagued InnoDB since the beginning.  Fortunately it affects only a small percentage of queries.

Upgrade to a recent 5.6.  There is a significant improvement wherein the stats are no longer recomputed whenever you sneeze.  It is now essentially possible to set them once and forget them.  The number of "random dives" and which algorithm is used is now less important.

As mentioned, MariaDB (and eventually 5.7) has fancier statistics.