Primality testing (deterministic vs. non-deterministic)
The simple answer is that AKS horribly inefficient in the real world.
Even the asymptotic complexity is orders of magnitudes higher than the one of probabilistic algorithms. Here is a comparison of AKS with Rabin-Miller and other probabilistic algorithms.
The following table illustrates the problem nicely (The tested number was $10^{
100}
+ 267$: