If there are, say, ten thousand license plates of interest at any given time (which seems high), that’s what, 10KB? Not really that hard to update that every 15 minutes (or hell, every minute).
I don’t really see any drawbacks with storing them on the device, they should already be quasi-public knowledge (from warrants/etc) so it’s not like there’s a privacy/security risk there
You could just store it in a bloom filter, which would be non-public but also give you tunable accuracy. For 1 in a million false positives, a bloom filter would cost 28.8 bits per plate.