I told my robot companion ED-E to return to base and a notification popped up saying he would be waiting at the Lucky 38. It's been about two weeks ingame now and it isn't anywhere, not even Primm. When I try to recruit a new companion, it won't let me because it says I still have two companions(Boone and ED-E), but ED-E is no where in sight. The worst part is I don't even have the perk that you get from acquiring ED-E anymore. I have traveled to so many places and searched most of New Vegas, but unlike most people, my companion won't magically appear at some random moment. What can I do? I really need a different companion to start questing.

When Veronica disappeared on me it took somewhere around a week to receive a message saying that she had returned to her original location. You can try waiting out a week or so with the quick wait feature and see if you receive another pop-up message telling you that ED-E has returned (it should give you the location in the message.)

That was the first thing I tried when this happened, but I got no message. I've checked Primm and the Lucky 38, but to no avail. My fear is that ED-E got stuck somewhere behind a rock or something on the way back. The Mojave Wasteland is a big place for a small robot, and I'm not about to waste my time looking for him just to tell him to leave my party. I think the only thing to do is start a new character so I'm going to finish the story and start all fresh again. Thanks for the advice though.

It might be worthwhile to continue on with missions that won't require the help of two companions and see if the script eventually triggers. If the AI works as it did in Oblivion, the complexity of AI behavior scales down drastically the further you travel from their location. So, if you are on the other side of the wasteland there is no use for ED-E's pathfinding AI, and it would simply calculate the time to travel, or one can only hope, magically appear... somewhere?