Si que puedes colocar los datos de patentes a borrar en otra hoja, de echo tienes que hacerlo porque si no no va a funcionar.
Al no poder pasarme la hoja no puedo generarte la macro porque sería complicado. Tu después no sabrías adaptar el código de visual basic para que funcione correctamente en tu hoja.
Otra forma sencilla en 2 pasos es utilizar la formula =consultav (también puede sr =buscarv o =vlookup dependiendo de la version o el idioma).
Primeo en una hoja nueva copia todas las patentes (45) en la columna A.
Después en una columna nueva en la hoja de los 5000 registros, introduces la formula de esta manera en la primera celda donde tenga patentes a borrar y luego la copias hasta el final de la hoja:
=consultav(A1;hoja2!A:A;1;falso)
Si la patente de esa línea está en el listado de las 45 patentes aparecerá su nombre, de lo contrario aparecerá #N/A. Ahora sólo tienes que filtrar esta nueva columna por #N/A y las borras.
Ya está listo.