Moved site to new, similar server - same query is taking 10x longer?
The fast query avoids sorting the result by reading in date_recorded index order matching your ORDER BY. It filters the hard way, comparing your conditions in the WHERE clause to rows one by one, but once it gets enough matching rows to satisfy the LIMIT, it stops scanning the table.
Whereas the slow query tries to use indexes on a couple of columns, thinking this will help. But it ends up having to scan hundreds of thousands of rows to find those that match, then finds the set of rows that matched both index searches (that's the Using intersect note), and finally sorts the large set of rows the hard way, using a filesort, just to return 16 rows and discard the rest.
This is a good counter-example case that shows that searching by index isn't always the best strategy. But the MySQL cost-based optimzer is biased to think that searching by index is usually better.
In this case, you might want to use an index hint to make it choose the date_recorded index.