Searching large dataset, best way to speed this up

I'd do a JOIN instead of the the inner query. That is still costly, but it's done once for all entries instead of once per entry.

Only problem would be that you might get duplicates IF multiple rows in quotes match the id of an entry in vehicles. In this case you can do the join to select the ids and then just join against that again (assuming the id is a PK in vehicles) to get the actual entries.

The other answers have almost gotten there.

SELECT  *
    FROM  vehicles v
    WHERE  v.group_id = 0  -- Note: Typo?  `group_id`, not `group`
      AND  EXISTS 
    (
        SELECT  1         -- Note: simply "1" (or almost anything)
            FROM  quotes quote
            WHERE  quote.vehicle_id = v.id
              AND  quote.term = 60
              AND  quote.annual_mileage = 8000
              AND  quote.deposit = 250
              AND  quote.credit_rating = "Excellent" 
                         -- Note: group by not needed
    )                    -- Note: NULL check not needed

And, yes:

quote:  INDEX(credit_rating, deposit, annual_mileage, term, vehicle_id)
        -- Your existing `covering_ndx1` is fine.
vehicles:  INDEX(group_id, id) -- (may not be used; depends on frequency of `group_id = 0`)

Yes, an index on quote.vehicle_id would help this greatly.

As a general rule^† it is a good idea to have an index on columns that are foreign keys, and you should define it as a foreign key with:

FOREIGN KEY (vehicle_id) REFERENCES vehicles(id)

This way the database will help verify your data and prevent a family of potential bugs happening.

Also you will find mySQL's query planner/engine produces a more efficient plan if you use WHERE EXISTS. Your sub-select with GROUP BY will force it to run that part once per outer row when more efficient strategies could be available. Also EXISTS can exit early, once the first matching row is found, but a subquery with an aggregate as above will stop that happening so more rows may be read and considered which is not needed:

SELECT *
FROM vehicles v
WHERE v.group = 0
AND EXISTS (
    SELECT id FROM quotes quote
    WHERE quote.vehicle_id = v.id
    AND quote.term = 60 
    AND quote.annual_mileage = 8000
    AND quote.deposit = 250
    AND quote.credit_rating = "Excellent"
    ) 

You still want the index on quote.vehicle_id for this to avoid full table scanning.

^{† There are valid exceptions to this rule, which is part of why most database engines don't create such an index automatically, but they are fairly rare.}

Create an index to support this

ALTER TABLE quote ADD INDEX covering_ndx1
(term,annual_mileage,deposit,credit_rating,vehicle_id);

The first four(4) columns support the JOIN and the last column supports the GROUP BY

I would also experiment with using the EXISTS clause

SELECT *
FROM vehicles v
WHERE v.group = 0
AND EXISTS (
    SELECT count(id) FROM quotes quote
    WHERE quote.vehicle_id = v.id
    AND quote.term = 60 
    AND quote.annual_mileage = 8000
    AND quote.deposit = 250
    AND quote.credit_rating = "Excellent"
    GROUP BY quote.vehicle_id
);