Query optimization when no row is returned
The best index for this query is (u1_id, t)

My initial guess was right, that you have indexes on (t) alone and on (u1_id) alone. You haven't told us the exact EXPLAIN output (which index is used), so the most probable explanation is that mysql is choosing to use one of these existing indexes or none at all (doing a full scan of the table), which yields the not so efficient plan.