Couple of ideas...
Let the TSA do the searches - this would give them a little actual practice in finding things that are being smuggled in, rather than the usual 'security theater' that is the case in the airports.
Use signal triangulation to find out where exactly the mobiles are, and therefore which prison cells to search.
Check the operators for mobiles which are ALWAYS connected to masts in the vicinity - almost nobody but a prisoner will NEVER leave the area. Then go after those SIMMs - get the numbers and find out who they are calling / texting. Should give a pretty good idea of who has the phone.
In the last resort they could take a lesson from the Afghans - point guns aggressively at the mobile operators until they shut down the masts, perhaps even blow a few up...
Why Paris? - read the last few words again...