It’s going to be difficult, I think.
What do you know about his last whereabouts and his plans? Do you know where he was staying? If so, you should probably call the hotel or guest house and see if he checked out and paid his bill or if he just disappeared.
If he paid his bill, he may have disappeared while trekking. Did he register his plans at the embassy before starting? He should have (but many trekkers skip it and those that do register often give only the sketchiest of details about the itinerary). Do you know if he planned to use a trekking agency or just go independent (and possibly hook up with people informally)? If he was using an agency, you should definitely call them and see what they know.
There are two “standard” ways to trek to the Everest region (unless you’re really hardcore or just deliberately trying to do something different): Take the bus to Jiri and walk from there, or fly to Lukla and skip the less scenic areas. If he flew to Lukla (which is the more popular option), there should be airline records. Call every airline in Nepal and see if he bought a ticket to Lukla.
While trekking, there are police checkposts where you are supposed to sign in as you go along. While it’s possible to skip some of these, it’s very hard to bypass the one at the entrance to the Sagarmatha National Park (where you have to get your permit stamped). If you or someone you trust can take a look at that log book, you can find out if he made it that far. Personally, I wouldn’t try to do this by phone, though. Communications are tricky and I wouldn’t trust the folks at the checkpoint to do a really thorough job unless I was looking over their shoulders…
You may also want to contact the following organizations in Kathmandu and see if they can offer any assistance.:
The Himalayan Rescue Association helps with mountain rescue and also has a post at Pheriche on the trail to Everest. Most trekkers stop there for the lecture on altitude sickness. He might even have signed the logbook there.
The Himalayan Explorers Connection has a nice office and noticeboard where people can find trekking partners. I found the people there to be knowledgeable and extremely helpful.
The Kathmandu Environmental Education Project (KEEP) is another organization that’s popular with trekkers. They give advice on trekking and also have a board where people can find trekking partners.
My guess, though, is that he didn’t disappear while on the trail. Lots of people (both tourists and locals) use those trails. When a tourist was killed on the trail in the Annapurna region in 1999, everyone knew about it. I heard that piece of gossip multiple times from different people–so it’s not like a tourist can just die on those trails and not be noticed…
The only thing that I don’t know about is the Maoists. When I did the Everest trek in 1999, they weren’t really an issue. Even when the Maoists were active, they avoided targeting tourists. Some trekking parties got hit up for “taxes”, but kidnappings certainly didn’t seem to be the Maoist’s style. And there’s been a ceasefire between the government and the Maoists since late January, so you wouldn’t expect there to be a lot or problems. You might want to ask the people at the HRA or HEC if they heard of any problems with the Maoists in the Everest region this spring.