"Lost in the mists of time" is the typical phrase. The other is not and may come from people mishearing the phrase or people wanting an alternative construction (with a different meaning). If you do insist on using the latter, then it makes more sense to say, "lost in the midst of time" or "lost amongst moments of time".
I would read the two differently in the first place, though. The "mists of time" indicates something long ago, "lost in the fog" as it were. Being "lost in the midst of time" would indicate you're lost in the middle of time, which doesn't have any clear meaning to me unless you're a time-traveler. NewAlexandria's answer points out one potential reading (many online do, in fact, turn out to involve time travel or weird, mystical experiences that deviate from the typical phrase and its meaning).
The phrase "midst of time" does return plenty of results in Google (~80 000) but not nearly as many as "mist of time" or "mists of time" (~4 000 000). People may certainly extract meaning from using midst, as long as they're using it for the right purpose. They do not express the same thing.