I've been running a simulation for a while starting at 2^(2^8) checking for Fermat possible primes base 2. So far it's listed about 1 in 180 numbers as possible primes. By the prime number theorem, I believe you would expect about 1 in 177 numbers as actual primes at this range, so odds are it is reporting few if any actual Pseudo-primes.
I could start to run a full prime certification on these but a) That's going to take quite a while, currently odds are nearly all of these numbers are prime so there will be next to no fast rejections and b) that isn't going to help estimate at other ranges - such as 2^2^16, which I am currently more interested in, but is prohibitively expensive for me to search at to any degree of statistical usefulness.
Note, I am not looking for, "for a particular N what is provable maximum probability of K being a Fermat liar (if N is not Carmichael)" which is what searching really wants to show me, but rather more: "for a particular K, roughly how many integers in the range N to M should we expect K to be a Fermat liar for, for large N,M".
Edit1: I left the simulation running overnight, and after 50M tests it has converged to roughly 177.34 as the gap between found primes as opposed to a gap of 177.44 indicated by the prime number theorem, so virtually all of the possible primes are actually prime and 2 is going to be a Fermat Liar for this range with very very low probability (as it is not a liar for most of the potential primes, and obviously a liar for none of the rejected numbers). I guess the next step for me is actually running some primality proofs to get some exact numbers.
Edit2: Testing against 11 bases in the strong pseudoprime test (should be enough to expect not much more than 1 false positive in ~4M primes in the worst case) run against the first 200K possible primes found, and only the second number in the range (2^2^8+1) was both flagged as a probable prime but did not pass all 11 rounds. This suggest (but does not prove) Fermat Liars are vanishingly rare as N gets large, save for numbers of some special form.