Let E be an elliptic curve defined over a number field K with ring of integers R. We consider the set S of all the orders of reductions of E modulo the primes of R. Given an integer m > 1, one may ask how many residue classes modulo m have an intersection of positive density with S. Using results of Serre and Katz, we show that there are at least two such residue classes; except for explicit families of elliptic curves and corresponding values of m. We then describe this exceptional set of elliptic curves and list the values of m when K is of degree at most 3; or K is Galois of degree 4.