Используйте метод RichTextBox.GetFirstCharIndexFromLine (), чтобы узнать, куда вставить текст. Например:
int prev = richTextBox1.SelectionStart;
int cnt = richTextBox1.Lines.Length;
for (int line = 0; line < cnt; line++) {
richTextBox1.SelectionStart = richTextBox1.GetFirstCharIndexFromLine(line);
richTextBox1.SelectionLength = 0;
richTextBox1.SelectedText = DateTime.Now.ToString() + ": ";
}
richTextBox1.SelectionStart = prev;