Filtering a MySQL table on multiple columns, including one with spatial data
You are saying that some type_keys are associated with thousands of rows; some with only a few?

An off-the-wall thought:

if ( SELECT id FROM edges
         WHERE type_key = ? AND deleted IS NULL
         LIMIT 100, 1 ) is NOT NULL
then
   SELECT * FROM edges ... FORCE INDEX(type_key) ...
else
   SELECT * FROM edges ... IGNORE INDEX(type_key) ...


Caveats:


The IF statements require either using a Stored Procedure or moving the IFs into your app code.
I don't know if the idea will work.
The choice of 100 needs tuning.