To anyone who has lost Ed-e around Nellis Air Base, I'm here to tell you it almost certainly happened during your initial approach, amongst artillery fire. Ed-e seems to get knocked through the environment by explosions, and this is one area it seems to happen in the most.
Any advice that can be offered on getting him/her/it back (without console commands, us po-boys are still rockin' the 360) would be appreciated.

Do what I did, have him wait by the road where the guy tells you about the bombing you need to dodge.

I almost always post my companions out of dangerous areas. Just fast travel back to them once you discover your intended location. Also, if they get lost try finding them at their original location (Ed-E at Primm). It may take days or as long as a week in game time for them to return unless they are dead.

On this note it wouldn't be awful to have companion markers on the map and maybe a journal that details events youve had "Ed-E has died" or "you have become vilified by the Boomers" ie. Sometimes my Ed-E will die and I won't get any announcement while I stare at his "corpse".

Yeah, combat and/or text log of some sort would go a long way to helping people run down any problems they might be having. I often wish I had a log where I could go back and read over what exactly I was told by an NPC in regards to a quest.

Exactly. Usually things are detailed in notes but some sub quests are harder to remember without wiki...like the sunset sarsaparilla star cap challenge.