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?
Technically, IMSI is not a device identifier. MT has IMEI and SIM (or more precisely ICC) has ICCID (which is normally never transmitted over the network). And the legislation probably specifically targets spoofing the IMEI, as spoofing IMSI does not gain you anything other than absence of service (on normal GSM/3GPP network).
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).
Like anything, it is technically possible to do this. As a defensive mechanism, I think it would make sense to perhaps hang out at city call and collects a bunch of IMSI's worth spoofing, and then rebroadcast those while you were being subject to surveillance, the goal being to force the adversary to follow down a bunch of leads which are bogus.
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.
SDRs are no longer that expensive - even an Ettus or BladeRF device is within the range of the average middle-class engineer - and can be programmed completely in software to act as a cellular baseband device.
Yes, but the value of the collected data is much reduced if you can't distinguish between legitimate IMSIs and spoofed IMSIs of devices that were never actually there.
No, because he who collects isn't interested in random mobile phones, and whoever tries to spoof "other" phones doesn't know the phones of interest of the collector. And the collector is interested not in knowing the presence but in the whole traffic, so the spoofing is even more obvious.
If you attach to a network successfully, it means the its secret key stored in the SIM card matches that of the network.
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.
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.