Попробовал, всё работает, RowAdded не использую вообще

Единственное, что надо соблюдать порядок:

dataGridView1.RowTemplate.HeaderCell = new DGVRowHeaderCell_T001();
dataGridView1.DataSource = table;

а не наоборот.

Куски кода:

        private void Form1_Load(object sender, EventArgs e)
        {
            DataTable table = new DataTable();
            DataColumn column0 = new DataColumn("icon", typeof(Icon));
            DataColumn column1 = new DataColumn("description", typeof(string));
            table.Columns.Add(column0);
            table.Columns.Add(column1);
            DataRow row = table.NewRow();
            row[0] = this.Icon;
            row[1] = "desc1";
            table.Rows.Add(row);
            row = table.NewRow();
            row[0] = Icon;
            row[1] = "desc2";
            table.Rows.Add(row);
            dataGridView1.RowTemplate.HeaderCell = new DGVRowHeaderCell_T001();
            dataGridView1.DataSource = table;
        }

    public class DGVRowHeaderCell_T001 : DataGridViewRowHeaderCell
    {
        #region Methods

        private Icon GetIconForDraw(int index)
        {
            try
            {
                DataRow item = ((DataTable) DataGridView.DataSource).Rows[index];
                return (Icon) item[0];
            }
            catch
            {
                return null;
            }
        }

        #endregion

        protected override void Paint(Graphics graphics, Rectangle clipBounds, Rectangle cellBounds, int rowIndex, DataGridViewElementStates cellState, object value, object formattedValue, string errorText, DataGridViewCellStyle cellStyle, DataGridViewAdvancedBorderStyle advancedBorderStyle, DataGridViewPaintParts paintParts)
        {
            base.Paint(graphics, clipBounds, cellBounds, rowIndex, cellState, value, formattedValue, errorText, cellStyle, advancedBorderStyle, paintParts);
            Icon ico = GetIconForDraw(rowIndex);
            if (ico != null)
            {
                graphics.DrawIcon(ico, cellBounds);
            }
        }
    }