I've read carefully this question posted 4 years ago: Adding "re" prefix
You can't use the prefix re- in any verb. Rebe, rebelieve, rehave, etc.
However there are plenty of verbs that use such a prefix.
The dictionaries do not help:
Relearn does not appear in online dictionaries such as:
or Cambridge (http://dictionary.cambridge.org/spellcheck/english/?q=relearn).
Unlearn , for instance, appears in both :)
It seems a trivial issue for a native speaker but sometimes is hard for an English learner to guess whether verbs can have the re- prefix or not.