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.)
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.
However, running it with k=50 gave a random set of them each time. So perhaps the probability data I gave was not right.
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.
(a^6)^144 = (0^6)^144 = 0 mod 7.
We can confirm this (using python):
>>> (7864)%1729
742L
Still, the density of values not relatively prime to a Carmichael number is asymptotically zero, so the test is still broken.
742
Pick a = 1722.
a^[(n-1)÷2] mod n = 742
Therefore 1729 is composite.
The test seems to hold, here.