Learn English – the history of adding the a- prefix to form words

In short:

• In Proto-Germanic, the prefix was *ga-;
• In Old English, it was ġe- (pronounced /je/, /jə/);
• In Middle English, it was y-, i-, or ȝe- (pronounced /ɪ/);
• In Modern English, it survives in a handful of words as i-, a-, or y- (see below).

The Wiktionary page for y- has these usage notes:

This prefix represents a common Germanic perfective prefix which was used to form past participles. Already by the Old English period such participles could be used with or without it, and as it passed into Middle English forms y-, i-, and ȝe-, it became less productive. The prefix was later adopted as a conscious archaism by some writers such as Edmund Spenser, who prepended it to existing past participles.

Etymonline has this to say about y-:

perfective prefix, in y-clept, etc.; a deliberate archaism, introduced by Spenser and his imitators, representing an authentic M.E. prefix, from O.E. ge-, originally meaning "with, together" but later a completive or perfective element, from P.Gmc. *ga-. It is still living in German and Dutch ge-, and survives, disguised, in some English words (e.g. alike, aware, handiwork).

Finally, the Merriam-Webster has this discussion of yclept:

"Clepe" itself is a word that is considered archaic and nearly obsolete, but its past participle "yclept" (pronounced ih-KLEPT) continues to be used, albeit rarely. In Old English, the prefix "ge-" denoted the completion or result of an action; in Middle English, the prefix shifted to "y-" and appeared in words such as "ybaptised" and "yoccupied." Eventually, all the "y-" words except "yclept" fell into disuse. One reason that "yclept" persists may be that it provides a touch of playfulness that appeals to some writers. Another may be that although "yclept" is an unfamiliar term to most people, its meaning can usually be inferred from context. Whatever the reason, "yclept" continues to turn up occasionally in current publications despite its strange and antiquated look.

Emphasis mine in all cases.

And yes, I realize that I haven't addressed the why part of your question.

Henry is of course technically correct: You can't just slap re- onto any verb. But I believe the spirit of your question is: Are there verbs that are correct to put re- in front of, even though the result is not in the dictionary? And further, are these plentiful enough that your friend was merely being sloppy in their phrasing, rather than wrong in spirit?

My answer: Definitely yes, and yes.

My dead-tree American Heritage Dictionary even has this note following its entry for re- (note the first sentence):

Usage: Many compounds other than those entered here may be formed with re-. In forming compounds re- is normally joined with the following element without space or hyphen: reopen. If the second element begins with e, it is preferable to separate it with a hyphen: re-entry. However, such compounds may often be found written solid and are indicated here as fully acceptable variants. If a compound that resembles a familiar word is intended in a special sense, the hyphen is necessary to make the distinction: re-creation, meaning "creation anew." The hyphen may also be necessary to clarify an unusual nonce formation: re-realignment, or a compound that produces a series of three or more vowels: re-aerify.