The earliest example seems to be in a flashback to 1943 in the episode "Why We Fight."
There's a timeline showing the times of all the flashbacks to earlier points in Angel's life here (there's also a longer list of flashbacks that includes comics here), and transcripts of Buffy and Angel episodes here and here. I did control-F to look for all the instances of the word "Angel" in the transcripts of these episodes which have flashbacks to after he'd been re-ensouled:
"Darla" (features flashbacks to 1760, 1880, 1898)--in 1760 The Master says "Angelus - the Latinate for Angel. (Laughs) It's marvelous", but I don't think that counts, and elsewhere in the flashbacks he is always called "Angelus."
"Becoming, Part I" (features a flashback to 1898)--this one shows the moment he was re-ensouled, but no one refers to him as "Angel" in the flashbacks
"Five by Five" (features flashbacks to 1898, before and after his re-ensoulment)--still referred to as "Angelus"
"Fool For Love" (features a flashback to 1900)--no one at the time referred to him by name
"Orpheus" (features flashbacks to 1902, the 1920s and the 1970s)--no one at the time referred to him by name
"Blood Money"--no actual flashback, but in this episode we meet a demon named Boone who tells Lindsey and Lilah at Wolfram & Hart that he wants to kill Angel, saying,"I've known Angel since Juarez in the twenties. We had a little disagreement over a senorita. I called him out. We fought for three and a half hours." That could indicate that at the time he knew him as Angel, but he could just be using that name because it's the one Lindsey and Lilah would be familiar with (and it was later shown in the episode that Boone and Angel had planned to trick the Lindsey & Lilah by making them a phony offer, so Boone had obviously gotten re-acquainted with Angel since the 1920s).
"Why We Fight" (flashbacks to him working for the government during the war in 1943): Here a military man says "Have you ever heard dying men screaming for their lives, Angel?", and a bit later a man in black says "You've been on our radar for some time now, Angelus", to which Angel replies "Name's Angel".
So aside from the slight ambiguity in what name he went under when Boone first met him, "Why We Fight" seems to be the earliest clear example.
