I was thinking about this problem again as well earlier today. The problem with trying to keep the number of times each deck has been played even would be that not all decks were submitted at the same time, so if you have a deck on day 5 and a bunch of new decks being added, the day 5 one won't get played much at all.
Another option though would be to remove the random factor altogether. Just have it start at the rank 1 deck, then the next game goes to rank 2, rank 3 etc until it hits rank 500 and then start over at 1 again. To prevent a deck from getting "extra" plays by losing one game, dropping in rank, and thus getting played again at the lower rank in the same cycle, the play order list could be updated ONLY when it starts over at 1 again. This should guarantee all decks get played equally. Depending on the number of other people playing, this should also make it highly unlikely that you run into the same deck repeatedly and thus prevent a particularly bad matchup one way or the other from having too great an impact on a deck's standing(especially early on, losing 2 in a row to the same person could have a very big impact on a deck's rank).