If somebody cannot be located, it's possible to get permission from a court to use "substituted service" - often involving some combination of public announcement or posting, and service on the person's last known address. But you have a valid phone number, so it should be possible for your process server to find him and effect service. If necessary you can subpoena his billing address from the cell phone company.