C#

for (int i = 0; i < zeroFrequencyLetterList.Count && decrypted < 25; i++)
                       {
                           bool flag = true;
                           Random r = new Random();
                           int randomed;
                           do
                           {
                               randomed = r.Next(0, zeroFrequencyLetterList.Count);//<--- here i get almost always '0', no meter how big the ArrayList, almost always it means that one in X executions i get different answer than '0'

                               if (encryptionKey[zeroFrequencyLetterList[randomed]] != ' ')
                                   flag = false;
                               else
                                   flag = true;
                           } while (!flag);

                           encryptionKey[zeroFrequencyLetterList[i]] = abcLetters[randomed];
                           abcLetters.RemoveAt(randomed);
                           zeroFrequencyLetterList.RemoveAt(i);
                           decrypted++;
                       }

 i   Count
===  =====
 0    10
 1     9
 2     8
 3     7
 4     6
 5     5

Random r = new Random();
                       int leftLetters = zeroFrequencyLetterList.Count;
                       for (int i = 0; i < leftLetters && decrypted < 25; i++)
                       {
                           bool flag = true;
                           int randomed;
                           do
                           {
                               randomed = r.Next(0, zeroFrequencyLetterList.Count);

                               if (encryptionKey[zeroFrequencyLetterList[randomed]] != ' ')
                                   flag = false;
                               else
                                   flag = true;
                           } while (!flag);

                           encryptionKey[zeroFrequencyLetterList[0]] = abcLetters[randomed];
                           abcLetters.RemoveAt(randomed);
                           zeroFrequencyLetterList.RemoveAt(0);
                           decrypted++;
                       }

i = 0;  list = 0, 1, 2, 3;  list[i] = 0;  remove i
i = 1;  list = 1, 2, 3;     list[i] = 2;  remove i
i = 2;  list = 1, 3;        list[i] = oops!

public override void Test(int arg) {
    int n=10;
    int max=1000000;
    if (arg==2) { n=10; max=1000; }
    if (arg==3) { n=3; max=100; }
    Random r=new Random();
    int[,] hist=new int[n,n];
    int prev=0;
    for (int i=0; i< max; i++) {
        int j=r.Next(0, n);
        hist[prev, j]++;
        prev=j;
    }
    for (prev=0; prev< n; prev++) {
        string s="";
        for (int j=0; j< n; j++) {
            s+=hist[prev, j].ToString().PadLeft(8);
        }
        log(s);
    }
}

using System;
using System.Linq;

namespace ConsoleApplication1
{
   class Program
   {
      static void Main(string[] args)
      {
         Tester();
         Console.ReadLine();
      }
      public static void Tester()
      {
         //Bogus variables to emulate code
         int[] zeroFrequencyLetterList = { 1, 2, 3, 4, 0, 5, 10, 9, 8, 7, 6, 5, 10, 2, 9, 7, 0, 6 };
         int decrypted = 0;
         char[] encryptionKey = { 'a', 'b', ' ', 'c', 'd', 'e', ' ', ' ', 'f', ' ', 'g' };

         Random r = new Random();
         for (int i = 0; i < zeroFrequencyLetterList.Count() && decrypted < 25; i++)
         {
            int randomed;
            char aLetter;
            do
            {
               randomed = r.Next(0, zeroFrequencyLetterList.Count());
               aLetter = encryptionKey[zeroFrequencyLetterList[randomed]];
               Console.WriteLine("{0,3}: {1,3} -> {2}", i, randomed, aLetter ); 
            } while (aLetter == ' ');

            //    encryptionKey[zeroFrequencyLetterList[i]] = abcLetters[randomed];
            //    abcLetters.RemoveAt(randomed);
            //    zeroFrequencyLetterList.RemoveAt(i);
            decrypted++;
         }
      }
   }
}