Thanks, Sean, for the clarification.
Actually ALL profiles had disappeard from the machines. What we did in the end was a combination of "Clear Certificate(s)" for each client (in FileWave Admin), add them again to Filewave when they appeard in "New Client from Server" window (there was no conflict to be resolved although the clients were still present in FileWave) and run the command "sudo profiles renew -type enrollment" on each client. We also did a "Clear Fileset Status" and a "Verify" for each client to better see, what was going on.
I'm not sure about the correct order and whether there are any reboots required/recommended between certain steps. Also we did a few model updates just to be on the safe side. It was try and error and some (more or less educated) guessing, but in the end we got all clients back and learned some lessons (lesson one: always double check the selected clients befor archiving them!)