Dominique,
I would guess that the varying query plans are a result of that InnoDB statistics in 5.5 and earlier is recomputed each time you restart the server. Different statistics may give different query plans. In other words, I do not think it has anything to do with slave status or not, but just that the statistics was changed when you restarted the server.
It is possible to improve the accuracy of the statistics by increasing the sample size (see this blog post:
http://oysteing.blogspot.com/2011/04/more-stable-query-execution-time-by.html). Doing that should give less variance in statistics and query plans.
In MySQL 5.6, InnoDB provides persistent statistics. This way, statistics will not change when a server is restarted. (See
http://dev.mysql.com/doc/refman/5.6/en/innodb-performance.html#innodb-persistent-stats)
Øystein Grøvlen,
Senior Principal Software Engineer,
MySQL Group, Oracle,
Trondheim, Norway