When the HS says 'Searching ..." it means it loses the connection with the base Telo. Most of the times, a reset on the HS will cure its problem. Some other times, a reboot on the base is needed too.
To reset the HS:
1. turn off the HS by press and hold the Red key.
2. press and hold the Left Soft key (i.e the left top most) and the '0' key
3. turn on the HS by press the Red key.
4. let go of the keys in step 2.
The HS will go straight to the 'Auto Registration' mode.
The 'A' key on the Telo has 2 functions
1. Paging: just a quick touch to page/find the HS
2. registration: touch/press and hold for few seconds to enter registration mode.
Thanks for the info, yes, it is a new system. I had called the company and they mentioned the left soft key and the zero key, but didn't mention that the phone should be off when doing that. So I tried what you said, held those two keys, the pressed the third key (which is not easy to do at the same time by the way), and the phone turned on. But it went immediately into "searching" mode again.
I rebooted the base unit as well. We are going to try moving the base unit to a different point in the network, between the modem and the router. I'll probably be back again, and thank you for the quick feedback.