Why does MySQL (InnoDB) table get faster after OPTIMIZE TABLE, but then don't work?
OPTIMIZE rebuilds the table.  This (for InnoDB) squeezes out some of the fragmentation and wasted space.  This is unlikely to make a noticeable difference in any query.

Also, OPTIMIZE does an ANALYZE.  This has a chance of changing the statistics, thereby leading to a different (better or worse) EXPLAIN plan.

Since ANALYZE is much faster (on InnoDB) than OPTIMIZE, just do the ANALYZE.

Various non-ANALYZE actions cause an ANALYZE to be done.

ANALYZE randomly probes the BTrees, gathering stats.  Sometimes the resulting stats are poor.  There is effectively no way to prevent this from happening.  Several partial hacks have been created over the years; 5.6.7 gets close to eliminating this problem with ANALYZE. Here's one of them: http://dev.mysql.com/doc/refman/5.6/en/innodb-parameters.html#sysvar_innodb_stats_persistent_sample_pages