Can $b^4+1$ be a pseudoprime to base 2 (except for Fermat numbers)? Cross-post: This very elementary question was first posted to Mathematics Stack Exchange but the response I got there (even after offering a bounty) was not useful.
For the purpose of this question, a pseudoprime is a composite number $n$ satisfying $2^{n-1} \equiv 1 \ (\text{mod}\,n)$, also known as a (composite) odd, weak Fermat pseudoprime to base two.
If we look at $n$ of the form $n=b^2+1$ we find many primes ($b$ in OEIS A005574) and pseudoprimes (A135590).
However, if we move to $n=b^4+1$ we still find many primes (A000068), but the only pseudoprimes we have been able to find are of the form $b=2^{2^k}$ which makes $n=b^4+1$ a Fermat number (which is obviously either prime or pseudoprime).

Question: If $b^4+1$ is composite but we still have
  $2^{b^4} \equiv 1 \ (\text{mod}\ b^4+1)$,
  will $b$ necessarily be of the form $2^{2^k}$?

If there is no obvious reason why this should be true, can someone provide some heuristics on the "expected" asymptotic behavior
of such numbers $b$? A computer search seems to demonstrate that there are no examples $b \le 2\cdot 10^{10}$. Maybe there is a smarter way to locate an example?
Or maybe this has been asked/answered before in the literature?
 A: Carl Pomerance conjectured in
On the Distribution of Pseudoprimes, Math. Comput. 37, 587-593 (1981)
that for large $x$, the number of pseudoprimes $\leq x$ is
$$
  \frac{x}{e^{(1+o(1))\log{x}\frac{\log{\log{\log{x}}}}{\log{\log{x}}}}}
$$
If Pomerance's conjecture holds, for sufficiently large $x$ there are more
than $x^{\frac{3}{4}}$ pseudoprimes $\leq x$. Now there are also about
$x^{\frac{1}{4}}$ integers of the form $n^4+1$ in this range which are not
Fermat numbers. Since $\frac{3}{4} + \frac{1}{4} = 1$, common heuristics
suggest that for large enough $x$ there are coincidences, i.e. numbers
which are both of the form $n^4+1$ (and not Fermat numbers) and
pseudoprimes. Here we make the plausible assumption that the properties
"$n$ is a pseudoprime" and "$n$ is of the form $b^4+1$, but not a Fermat 
number" are independent of one another.
The lack of examples for small numbers is easily explained by the $o(1)$
term converging to $0$ only slowly -- in fact there are only $118968378$
pseudoprimes below $x = 2^{64}$, which is just about $x^{0.419} < x^{0.75}$,
cf. this table.
The probability that two random subsets of $\{1, \dots, 2^{64}\}$ of 
cardinalities $118968378$ and $2^{16}$ intersect nontrivially is pretty low.
Exact counts of pseudoprimes up to the fourth power of your search limit
$2 \cdot 10^{10}$ are not yet known, but it seems likely that $x$ must be
considerably larger to push the count of pseudoprimes $\leq x$ above
$x^{\frac{3}{4}}$. Thus finding an example of a pseudoprime of the desired
form by means of computation may be very hard.
