Apologies for this long, disorganized answer. I do not have an unconditional answer, and I'm not sure if I'm answering the right question.
http://oeis.org/A090659 may be of more interest. Note CRG4's comments about not knowing whether this sequence is infinite or not (which is the cause for a lot of my wandering discussion below).
Monier (1980) and Rabin (1980) both show the upper bound of 1/4. E.g. Monier 1980:
"Proposition 2. The failure probability alpha_n of Miller-Rabin's test is less than 1/4 for any composite n. One remarks that we cannot presently give an upper bound lower than 1/4 since we do not know whether the set of numbers approaching this value is finite or not."
AGP 1994 notes "A slightly stronger version of the result of Monier [M] and Rabin [R] mentioned in the introduction is that if n > 9 is an odd composite, then at least 3/4 of the integers in [1,n] are witnesses for n."
Also see the last paragraph of the accuracy section on Wikipedia:
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Accuracy_of_the_test. While not a primary reference, this does not show any new results contrary to the 1/4 limit, and also indicates the general point that on average the false acceptance probability goes down rapidly with the size of the input, but adversarial situations should assume the inputs may be near worst case numbers.
More discussion:
I do not have a proof that there are infinitely many numbers within a given epsilon of 25%. However, some anecdotal ways of seeing these. First, from the A141768 sequence:
1. wget
http://oeis.org/A141768/b141768.txt
2. perl -MMath::Prime::Util=:all -nE '($n) = /^\d+ (\d+)/; ($lb,$t)=($n-1,0); for (2..$lb) { $t += is_strong_pseudoprime($n,$_); } say "$n ",100*$t/($n-1);' b141768.txt
A similar method can be done with Math::Pari, using something like Hasler's is_A001262() function in A001262. This is brute forcing the search -- the method in A141768 may be faster.
This may be easier to see by using A090659 instead, as it by definition will give a monotonically increasing sequence. If the sequence is infinite (conjectured but not proven), then I think we could make a precise statement such as "For any given epsilon > 0, there exists a c_0 such that there are infinitely many composites n > c_0 having at least (n-1) * (1/4 - epsilon) non-witnesses."
Monier (1980) breaks the composite n's into three categories. The last are non-Carmichael numbers, with the maximum P(n) occurring with two factors of form (2p+1)(4p+1) for odd p. We can do a similar experiment:
perl -MMath::Prime::Util=:all -E 'forprimes { $p=($_-1)>>1; ($p1,$p2) = ($_,2*($_-1)+1); if ($p & 1 && is_prime($p2)) { $n = $_*$p2; ($lb,$t)=($n-1,0); for (2..$lb) { $t += is_strong_pseudoprime($n,$_); } say "$n ",100*$t/($n-1); } } 9,10**12;'
and see a similar pattern, with monotonically increasing percentages (note: Higgens conjecture 2 shows it is monotonic, though just a conjecture). Monier notes it is an open question as to whether this sequence is infinite or not.
For one of the other cases, Carmichael numbers, there are infinitely many Carmichael numbers (AGP 1994), but I am not sure that this includes the subset we care about, with exactly three prime factors each congruent to 3 mod 4. See section 3 of AGP 1994.
Rabin (1980) discusses these numbers on page 133, but mostly noting that they exist hence reducing the constant 3/4 seems not to be possible. I did not see discussion of frequencies or distributions of these numbers.
The papers by Kim and Pomerance (1989) and Damgård, Landrock, and Pomerance (1993) may have more information. They are looking at the average probability of accepting a composite number, which is what we care about in a non-adversarial situation, and why for most cases (i.e. where the user isn't actively trying to find faults) the isprime function works pretty well.
According to the text in A141768, the sequence is infinite, but that would be true with the much weaker proposition that the absolute number of bases increases, allowing a decreasing percentage. I am unable to parse the AGP 1994 paper well enough to see if there is more information. Note that this follows from the comments in the sequences A141768 and A090659 -- the former is known to be infinite, while the latter is implied by Dickson's conjecture, but not proven.
Maybe I'm not understanding the question. As far as I know, the limit of 3/4 is the best limit known. Are you thinking that numbers requiring near that limit do not exist? [Rabin 1980 says they do, as do the programs above] That they are not infinite? [still an open question]. That "close to" is not precise enough? [granted, though we can conjecture a precise statement]
Thanks,
Dana
