Like most people I got saddled with Lydia after satisfying the first Jarl. She was fine, albeit with the personality of a wet dishrag. Anyways it's because of this that I was playing and then randomly noticed that she wasn't with me anymore. I didn't dismiss her, and I was pretty sure (but could not verify) that she didn't die in combat. By the time I realized this I had about another hour worth of playtime from when I last remembered seeing her so I didn't feel like going back to get her.

Next I ended up getting Marcurio on the recommendation of a number of other players (not to mention UGO.com rated him the 2nd best companion.) I found him much better, with an actual personality and some rather kickass magic skills. So we were adventuring just fine and then I went into a tomb only to turn around and realize that he was gone! I was flabbergasted. I even went back to Riften to see if he was in the tavern and he wasn't there either. However unlike Lydia I actually wanted Marcurio so I had to backtrack about an hour to get to an earlier save (which was conveniently right in the middle of a dragon battle) to get him back.

Is anyone else experiencing this?? Am I the only one who's having companions randomly disappear? I didn't pay as much mind with Lydia because she appears to be a somewhat glitched character anyways, but to have 2 separate companions disappear leads me to believe something is wrong.

Companions can get lost or stuck if you're not careful. He might also have died. There's really nothing you can do but learn to pay attention as to the whereabouts of your followers.

I've had issues with companions just disappearing off the face of Nirn in the following instances:

- telling them to wait somewhere. Usually having them wait somewhere isn't a problem, but in one memorable instance I told Erik to wait while in Helgen (on a re-visit, not during chargen/tutorial, obviously!), came back ten minutes later and he was gone. Trying to move myself to him via the console dropped me in the middle of Rorikstead, but still no sign of Erik.

Helgen in general seemed a bit buggy--lots of collision issues and dead NPCs disappearing, so I think that might have been what did it. He probably fell through the worldspace or something. Reloaded and kept him follow mode while in Helgen from then on.

- while using the map-based fast traveling. In fact, this happens almost constantly, especially if I fast travel to a city interior. In one instance I fast traveled to Kynesgrove, lost Meeko on cell load, then fast traveled again to Solitude and lost Erik too! As if I needed more motivation not to use fast travel.

- rarely on a standard cell load, while going from an interior to an exterior. Usually this happens for me with Meeko, not Erik, and for some reason the pup just hasn't followed me out of a door properly. If I return to the interior I just left he'll be there, still in follow mode. If I tell him to wait, then to follow again, all is fixed.

TL;DR: something is a bit buggy with companions, yes. I avoid it by not using fast travel and adopting my old Morrowind companion-based paranoia tactics (IE, turning around while walking every ten minutes or so to make sure they're still there).

Nvr lose them, tho forgetting that they are in Wait mode somewhere inaccessible can be a bother.

Got a msg recently that Lydia got tired of waiting and left; think that happened b4; she stayed in place in Breezehome last time that happened, but required being told to join up.

If you don't mind using the console, you can use the commands:

prid (followed by the relevant follower identification number)

moveto player

This moves the follower to the player's position and is fully documented http://www.uesp.net/wiki/Skyrim:Console.

I prefer this to moving to the follower - on one occasion, this resulted in appearing high above the ground, lookin at Lydia, and then watching gravity have the usual effect, just like Douglas Adams' bowl of petunias.