Converting from binary to unary
You are not supposed to replace all matches but only the first one. And then repeat the process.

Here is some javascript code that implements the markov algorithm exactly the way it is described on the wikipedia page.
Now all you have to do is translate that to C#.

function binaryToUnary(value) {
  var matchFound = false,
      rules = [["|0", "0||"],
               ["1",  "0|" ],
               ["0",  ""   ]];
  do {
    matchFound = false;
    for(var i = 0; i &lt; rules.length; i++) {
      var rule = rules[i],
          pattern = rule[0], replacement = rule[1],
          index = value.indexOf(pattern);
      if(index &gt;= 0) {
        value = value.substring(0, index) +
                replacement +
                value.substring(index + pattern.length);
        matchFound = true;
        break; //break because only the first pattern that matches should be replaced
      }
    }
  } while(matchFound);
  return value;
}