removeFrom[b_List, a_List] := Module[{f},
  f[_] = 0;
  (f[#] = -#2) & @@@ Tally[a];
  Pick[b, UnitStep[f[#]++ & /@ b], 1]
]

removeFrom[{a, b, c, a, d, a, e}, {a, c, a}]

{b, d, a, e}

removeFrom2[b_List, a_List] := Module[{f, g},
  (f[#] = -#2) & @@@ Tally[a];
  g[x_] /; f[x] < 0 := f[x]++;
  g[_] = True;
  Select[b, g]
]

short = RandomInteger[1*^5, 2*^4];
long  = RandomInteger[1*^5, 2*^5];

unsortedComplement[long, short] // Short // Timing
removeFrom2[long, short]        // Short // Timing

fastRF[a_List, b_List] :=
  Module[{c, o, x},
    c = Join[b, a];
    o = Ordering[c];
    x = 1 - 2 UnitStep[-1 - Length[b] + o];
    x = FoldList[Max[#, 0] + #2 &, x];
    x[[o]] = x;
    Pick[c, x, -1]
  ]

fastRF[{a, b, c, a, d, a, e} , {a, c, a}]

{b, d, a, e}

Needs["GeneralUtilities`"]

one = RandomInteger[1*^5, 1*^6];

BenchmarkPlot[
  {
   removeFrom2[one, #] &,
   unsortedComplement[one, #] &,
   uc[one, #] &,
   fastRF[one, #] &
  },
  RandomSample[one, #] &,
  5^Range[8],
  TimeConstraint -> 30
]

com = {a, c, a, a, b, c, a, d, a, e}
ord = Ordering[com]
com[[ord]]

{a, c, a, a, b, c, a, d, a, e}

{1, 3, 4, 7, 9, 5, 2, 6, 8, 10}

{a, a, a, a, a, b, c, c, d, e}

1 - 2 UnitStep[-1 - 3 + ord]
x = FoldList[Max[#, 0] + #2 &, %]

{1, 1, -1, -1, -1, -1, 1, -1, -1, -1}

{1, 2, 1, 0, -1, -1, 1, 0, -1, -1}

x[[ord]] = x; x

Pick[com, x, -1]

{1, 1, 2, 1, -1, 0, 0, -1, -1, -1}

{b, d, a, e}

Clear[unsortedComplement];
unsortedComplement[x_, y_] :=
  Module[{order, xsorted, distinct, freqs, posintervals, freqrules},
    xsorted = x[[order = Ordering[x]]];
    {distinct, freqs} = Transpose[Tally[xsorted]];
    freqrules = Dispatch[Append[Rule @@@ Tally[y], _ -> 0]];
    posintervals =
      Transpose[{
         Most[#] + Replace[distinct, freqrules, {1}],
         Rest[#] - 1
      }] &[Prepend[Accumulate[freqs], 0] + 1];
    x[[Sort@order[[Flatten[Range @@@ posintervals]]]]]]

unsortedComplement[{a,b,c,a,d,a,e},sub = {a,c,a}]

(* {b,d,a,e}  *)

large1 = RandomInteger[1000,10^5];
large2 = RandomInteger[1000,10^4];

(res1=unsortedComplement[large1,large2])//Short//Timing

(* {0.078,{951,956,345,459,345,951,956,<<89986>>,443,977,568,340,496,887,946}} *)

(res2=Fold[Delete[#1,Position[#1,#2,1,1]]&,large1,large2])//Short//Timing

(* {35.,{951,956,345,459,345,951,956,<<89986>>,443,977,568,340,496,887,946}} *)

res1==res2

(* True *)

uc[list_, eles_] := Module[{dt = Tally[eles], fm},
  fm = findMultiPosXX[list, dt[[All, 1]]];
  list[[Delete[Range@Length@list,
               Transpose[{Flatten[MapThread[Take, {fm, dt[[All, 2]]}]]}]]]]]

list1 = {a, b, c, a, d, a, e}; list2 = {a, c, a};
 Fold[Delete[#1, Position[#1, #2, 1, 1]] &, list1, list2]
 (* {b, d, a, e} *)

With[{patt = Table[Unique[], {Length[list2] + 1}]},
 ReplaceAll[list1,  Riffle[Pattern[#, BlankNullSequence[]] & /@ patt, list2] :> patt]]
 (*  {b, d, a, e} *)

{list1, list2} = {{a, c, a}, {a, b, c, a, d, a, e}};
Fold[# /. #2 &, list2, {h___, #, t___} :> {h, t} & /@ list1]
(* {b, d, a, e} *)

remover[long_List, short_List] := Module[{hmap, lookupresult},
  hmap = Language`HashMap@@Apply[Rule, Tally[short], {1}];
  Select[long, (lookupresult = Language`HashMapLookup[hmap, #];
     Or[lookupresult === $Failed, lookupresult === 0,
      (hmap = Language`HashMapAssociate[hmap, #, lookupresult - 1]; False)]) &]
  ]

simple[h_, p_] :=
 Join @@ (Table[#[[1]], {#[[2]]}] & /@
    Cases[Last@
      Reap[Sow[1, #] & /@ h; Sow[-1, #] & /@ p, _, {#1, Total@#2} &],
     Except[{_, 0}]])

{a, b, d, e}

comp[x_, y_] := Module[{},
  fun[q_] :=
   If[Length[q] == 1, q,
    Drop[#[[1]], Length[#[[2]]]] &@GatherBy[q, Sign]];
  ls[u_, v_] :=
   Cases[Last@
     Reap[Join[Table[Sow[j, u[[j]]], {j, Length[u]}],
       Table[Sow[-j, v[[j]]], {j, Length[v]}]], _, {#1, fun[#2]} &],
    Except[{_, {}}]];
  ord[u_] := Module[{pos, tab, or},
    pos = Flatten@u[[All, 2]];
    or = Thread[Sort[pos] -> Range[Length[pos]]];
    tab = Table[1, {Length[pos]}];
    ReplacePart[tab,
     Flatten@(Thread[#[[2]] -> #[[1]]] & /@ (u /. or))]];
  ord[ls[x, y]]]

{b, d, a, e}

v1 = {a, b, c, a, d, a, e};
v2 = {a, c, a};

Flatten[Table @@@
  Normal[Fold[
    Function[{ass, ele}, <|
      KeyValueMap[
       If[#1 === ele, #1 -> If[#2 - 1 >= 0, #2 - 1, 0], #1 -> #2] &,
       ass]|>], Length /@ PositionIndex[v1], v2]]]