Thanks so much guys, specially kennethyoung.
Had the "permanent searching" thing on my 5s (German O2) for 2 days, not responding to taking out the sim at all.
Previously it happened 2 times, once I did a simple restore, once I did the update to 8.1.3 to solve the problem.
This time I have been with it at the Genius Bar and they told me, they had no solution but to replace my phone (out of warranty, 2xx €).
Though they were not sure if it could be a problem with an app.
So they told me to try a restore from DFU mode first.
That brought my phone into a state I could not recover from. I tried maybe 30 installs with different firmwares, different computers, Win and Mac, always ending with "error -1" during "installing firmware".
By then I was completely sure my phone was done for and I was considering taking a replacement or upgrading, when I happend to come across this thread.
I put it into a plastic bag, put it into the freezer at -18°C for an hour and after that did the complete restore while it lay in there.
It worked without a single hicup and has been fine since then.
I´m really grateful, guys!
So far, has anyone been able to find out, where that annoying "searching" bug comes from?