hai ragione
dicevo per lo stringBuilder

codice:
string s = "xxxx#xxxxxxxx#xxxxxxxx#xxxxxxxxxx";
            int index = 0;
            int c = -1;
            StringBuilder sb = new StringBuilder("{0}");
            while (true)
            {                
                index = s.IndexOf("#", index);
                if (index < 0) break;
                sb.Replace(c++.ToString(), c.ToString());
                s = s.Remove(index, 1);
                s = s.Insert(index,sb.ToString());
            }
così? secondo te è meglio?