The MMO City of Heroes did something similar to this. They called it the streak breaker: http://cityofheroes.wikia.com/wiki/Attack_Mechanics#The_Stre...

Basically, the higher your chance to hit with an attack was, the the sooner it would break a streak of misses and force a hit. This is definitely not random, but seems to be more satisfying to the player. Plus it no doubt cuts down on the number of complaints on the forums about "unfair" RNG.