A slightly different approach:

We can consider a stripe of characters of the length from 5 to 10 and then shift in a band of 10 placeholders, surrounding by all possible tuples of other characters. Also, note that we should surround this stripe by alternative characters and only then consider tuples for the remaining placeholders on the left and on the right (depending on the shift), since we don't want to create a sequence of n+1 characters. Thus we eliminate almost all redundancies.

halfList[l_, nmin_] :=
  Flatten[Map[Flatten, ({n} \[Function]
       (stripe[ft_, lt_, pos_] :=
         Flatten@Join[
           If[pos > 2, {ft}, {Nothing}],
           If[pos > 1, {"b"}, {Nothing}],
           Table["a", n],
           If[pos < l - n + 1, {"b"}, {Nothing}],
           If[pos < l - n, {lt}, {Nothing}]
           ];
        stripeList[pos_] := 
         Outer[stripe[#1, #2, pos] &, 
          Tuples[{"a", "b"}, Max[0, pos - 2]], 
          Tuples[{"a", "b"}, Max[0, l - n - pos]], 1];
        shiftedList = stripeList /@ Range[1, l - n + 1]
        )) /@ Range[nmin, l - 1], {-2}], 3];

Cases[StringJoin @@@ halfList[10, 5], Except["aaaaabbbbb"]]

This only does half of the list, and the Flatten piece is sloppy, but the performance is actually quite decent, on par if not better than march's code. I might improve it later on.

A slightly different approach:

We can consider a stripe of characters of the length from 5 to 10 and then shift in a band of 10 placeholders, surrounding by all possible tuples of other characters. Also, note that we should surround this stripe by alternative characters and only then consider tuples for the remaining placeholders on the left and on the right (depending on the shift), since we don't want to create a sequence of n+1 characters. Thus we eliminate almost all redundancies.

halfList[l_, nmin_] :=
  Flatten[Map[Flatten, ({n} \[Function]
       (stripe[ft_, lt_, pos_] :=
         Flatten@Join[
           If[pos > 2, {ft}, {Nothing}],
           If[pos > 1, {"b"}, {Nothing}],
           Table["a", n],
           If[pos < l - n + 1, {"b"}, {Nothing}],
           If[pos < l - n, {lt}, {Nothing}]
           ];
        stripeList[pos_] := 
         Outer[stripe[#1, #2, pos] &, 
          Tuples[{"a", "b"}, Max[0, pos - 2]], 
          Tuples[{"a", "b"}, Max[0, l - n - pos]], 1];
        shiftedList = stripeList /@ Range[1, l - n + 1]
        )) /@ Range[nmin, l - 1], {-2}], 3];

Cases[StringJoin @@@ halfList[10, 5], Except["aaaaabbbbb"]]

This only does half of the list, and the Flatten piece is sloppy, but the performance is actually quite decent, on par if not better than march's code. I might improve it later on.