how can I calculate $a_{n+3}=a_n+a_{n+1}+a_{n+2}$?

Nest[] is in fact usable here, if you are ingenious enough and willing to wait a little:

Last[Nest[Append[Rest[#], Mod[{1, 1, 1}.#, 100000]] &, {1, 1, 1}, 20000000 - 3]]
   16287

An alternative is to use an undocumented function for modular matrix exponentiation:

Mod[First[Algebra`MatrixPowerMod[{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}},
                                 20000000 - 3, 100000].{1, 1, 1}], 100000]
   16287

You need to use Set rather than Equal for the initial conditions.

Clear[a, n]

a[1] = 1;
a[2] = 1;
a[3] = 1;
a[n_] := a[n] = Mod[a[n - 3] + a[n - 1] + a[n - 2], 100000];
Last[a /@ Range[4, 20000000]] // AbsoluteTiming

(* {107.222, 16287} *)

Similar approach to JM...

mat = {{1, 1, 1},
       {1, 0, 0},
       {0, 1, 0}};

init = {1,1,1};

next[vec_] := Mod[mat.vec, 100000];

First@Nest[next, {1, 1, 1}, 20000000-3] // Timing

(*  {42.0625, 16287}  *)

Inspired by JM's second approach, but using what is documented...still pretty fast. I thought it might overflow, but no problem.

First@Mod[Mod[MatrixPower[mat, 20000000 - 3], 100000].{1, 1, 1}, 100000] // Timing

(* {0.03125, 16287} *)