Thanks for bringing this issue up. The behavior certainly appears inconsistent. I sent a report to our development team. It appears Marco Thiel provided a good work-around for this.

Watch this:

     RandomPrime[{100000, 499999}, {2, 2}]
         (* {{246251, 287611}, {415111, 277003}} *)

and now

     RandomPrime[{100000, 500000}, {2, 2}]
              (* {{457889, 394619}} *)

And additional observation: There are 2 prime numbers between 499,970 and 499990

     PrimePi[499999] - PrimePi[499970]
     (* 2 *)

So RandomPrime[{499970, 499999}, {2, 2}] returns these 2 numbers twice {{499979, 499973}, {499973, 499973}} since we asked for 2 by 2 output. But RandomPrime[{499970, 500000}, {2, 2}] returns these 2 numbers one time {{499973, 499979}}. Very strange why it does this when the top range goes over 499999.

So, I would say it looks like a bug.
Version 10.02, on windows 7, 64 bit