For any value 0 < a < n, a^((n-1)/2) = (a^6)^144 = 1^144 = 1 mod 7.
For any value 0 < a < n, a^((n-1)/2) = (a^12)^72 = 1^72 = 1 mod 13.
For any value 0 < a < n, a^((n-1)/2) = (a^18)^48 = 1^48 = 1 mod 19.
Thus 1729 will pass the Lehmann test for all a. (Unsurprisingly 1729 is a Carmichael number; not all Carmichael numbers will pass all Lehmann tests, but any number which passes all Lehmann tests will be Carmichael.)
And this gives us an infinite-under-random-primes class, too: If 12n+7, 24n+13, and 36n+19 are all primes, then their product will pass all Lehmann tests.
I'm pretty sure that the Alford-Granville-Pomerance proof of n^(2/7) Carmichael numbers can be extended to give the same order result for "Lehmann-Carmichael" numbers, but I'm not going to do it at 5:30 AM when I'm struggling with a 102F fever.
Thanks! However, I'm not quite convinced. I ran the given Scheme implementation with k=10000 and it correctly reported all the numbers at http://www.kobepharma-u.ac.jp/~math/notes/note02.html less than 4294967087 as composite. (4294967087 is the largest random number Racket can give.)
However, running it with k=50 gave a random set of them each time. So perhaps the probability data I gave was not right.
I can't tell you what your code is doing wrong, but I promise 1729 should pass the test you described.
EDIT: And of course I forgot about non-relatively-prime values. But those are asymptotically sparse; you're seeing a random set of pseudoprimes for k=50 because with that many trials you have a good chance of catching small primes, but for larger Carmichael numbers you'll need a very large number of trials to get good odds.
For any value 0 < a < n, a^((n-1)/2) = (a^6)^144 = 1^144 = 1 mod 7.
For any value 0 < a < n, a^((n-1)/2) = (a^12)^72 = 1^72 = 1 mod 13.
For any value 0 < a < n, a^((n-1)/2) = (a^18)^48 = 1^48 = 1 mod 19.
Thus 1729 will pass the Lehmann test for all a. (Unsurprisingly 1729 is a Carmichael number; not all Carmichael numbers will pass all Lehmann tests, but any number which passes all Lehmann tests will be Carmichael.)