I did come up with a "reduced" version of part of your condition Mod(Mod(1,n)+x,1+x^4)^n = Mod(1, n)*(1  x) for n == 5 (mod 8)
First, when n == 5 (mod 8), lift(Mod(1 + x, 1 + x^4)^n) is a polynomial of degree less than 4, in which the coefficients of x^3 and x^2 are always equal, and the coefficients of x and 1 are always equal and opposite.
Let a_{k} be the coefficient of x in lift(Mod(1 + x, x^2  2)^k). This is a "Fibonaccilike" sequence: a_{0} = 0, a_{1} = 1, and a_{k+2} = 2*a_{k+1} + a_{k}.
Starting with a_{1} we have 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...
When n == 5 (mod 8) the coefficients of x^3 and x^2 in lift(Mod(1 + x, 1 + x^4)^n) are divisible by n when n divides a_{(n+1)/2}.
Note that 5 divides a_{3} = 5 and 13 divides a_{7} = 169, but 21 does not divide a_{11} = 5741.
I have not checked for composite n == 5 (mod 8) which fulfill this condition. (As you have noted, to satisfy your condition, n also has to be a base2 pseudoprime.)
