Do IMSI catchers have any way of verifying the intercepted IMSIs are legitimate? If not, would it be possible to build a device to flood them with fake/spoofed IMSIs?
Technical ability wise, yes.
Legally, no. The Mobile Telephones (Re-Programming) Act 2002 [0] makes spoofing IMSI, even that of your own, illegal in the UK.
[0] https://www.staffordshire.police.uk/info_advice/crime_preven...
Disclaimer: I am not a lawyer.
> he changes a unique device identifier,
Technically correct for technical discussions is not the same as contextually correct in a court room.
You will change your IMSI by simply changing the SIM card.
If you use pre-paid sim cards then those usually have thin provisioning of IMSI numbers they network buys a certain amount and activates them when the SIM card is activated and deactivates them once the SIM card has been inactive or not been topped off for a certain period of time (usually around 90 days).
When some one has your IMSI they can tie it directly to your personal details, phone number and various other details if they have sufficient access to the global cell system they can also get your location and what tower you are connected to. Historical log data will give them any tower you've been connected too from the first tower during the initial activation and provisioning to the last tower you've been connected too. Depending on the network and device most phones also send out nice diagnostic information about other towers and networks they see all the time regardless of what tower they are connected too at the time that with a given IMSI number will allow some one to triangulate the position of the device to under 10M in most urban areas if some one knows your IMSI they can pretty much pin point what room you are in at your house (give your house have several rooms pointing at different directions ;)).
From legal standpoint, device that spams IMSI catcher with registrations with random IMSIs is mostly same thing as the IMSI catcher itself, ie. device that requires it's own broadcast license to operate, as such device certainly does not meet legal (and technical) requirements for it to be an cellular phone.
On the other hand, generating random IMSI, burning that into ICC and thus producing unusable SIM is probably perfectly legal even when you put that inside normal GSM phone (from network standpoint it will behave mostly same as phone without any SIM). In practice SIMs with completely made-up IMSIs are even commercially available (idea there is that some phones will not fully boot without SIM).
That said, this is completely illegal (unlike the actual surveillance which has been made legal by a series of unfortunate events). So I would not advise anyone to do this. Not to mention that unless you design your own cellular baseband radio circuit (so that you have access to all the docs) building something like this with "off the shelf" parts is quite expensive.
https://en.wikipedia.org/wiki/IMSI-catcher
It doesn't have to "verify" what it collects.
Since your IMSI catcher is basically just a proxy between the mobile phone and the real network, you can therefore easily detect that the IMSI is who it says it is.