How can I speed up a DateTime comparison query in MySQL?
Take the 100ms query and LEFT JOIN it back to the locations table:

SELECT B.id, B.company_id, B.raw_address FROM 
(
    SELECT id FROM locations
    WHERE last_updated &gt; last_geocoded LIMIT 25
) A LEFT JOIN locations B USING (id)
WHERE B.raw_address IS NOT NULL;


Give it a Try !!!