what could make examined_rows change radically?
What is happening -- The Optimizer picked a different way to perform the query.

You are at the whim of


The Optimizer -- It gets better with each new version.
The statistics -- ANALYZE TABLE may help, or could hurt.  (OPTIMIZE is overkill, and ends with ANALYZE; "never" use it.)
The constants in the query -- May lead the optimizer to pick a different explain plan.
The "phase of the moon", as I call this combination of whims.


If id is the PRIMARY KEY and there is no JOIN, you are asking for a lot of extra work: COUNT(DISTINCT(t.id)),; switch to simply COUNT(*).

When a query is run, some EXPLAIN plan is generated.
When you use EXPLAIN, a plan is generated.
There is no guarantee that they match.  (This is solved only in the latest version, wherein the EXPLAIN is optionally included in the slowlog.

Any single-column index on any of these may be best; there is no way to know without a lot more info on the distribution of the data:  tag_1, tag_3, tag_4, site_id, message_time.  I would have several 2-col "composite" indexes starting with each and ending with message_time.  This way, if the query actually says foo IN (just-one-item), it can move past foo and also use message_time.

Before discussing further, please add SHOW CREATE TABLE.