Pues crea un bucle para recorrer todas las líneas, no solamente la línea cero, que es lo que estás haciendo en ese código.
Algo así como:
Código Delphi
[-]var iX : integer;
begin
for iX=0 to memo1.lines.count-1 do
memo1.lines[iX] := 'etiqueta1' + memo1.lines[iX] + 'etiqueta2';
end;