A.- Né en 1915, B._, ressortissant algérien, a
cotisé à l'AVS en 1963 et de 1966 à 1979. Résidant en
Algérie, il a présenté le 29 avril 1997 une demande de
remboursement des cotisations AVS.
Dans une communication du 6 février 1998, la Caisse
suisse de compensation a avisé B._ qu'ayant atteint
l'âge de 65 ans en 1980, il aurait fallu qu'il dépose sa
demande au plus tard en 1985. Attendu qu'elle n'avait pas
pu retrouver dans ses archives de demande de remboursement
avant 1985, tout droit au remboursement des cotisations AVS
était atteint de péremption.
B._, dans un écrit du 4 mars 1998, a répondu
qu'il n'avait cessé de réclamer le remboursement des
cotisations AVS depuis la fin de son activité "ou plus
précisément le 26/3/1979".
Par décision du 11 mai 1998, la caisse a rejeté la
demande de remboursement des cotisations AVS, au motif
qu'aucune demande ne lui était parvenue au plus tard en
1985, de sorte que "la prescription" s'appliquait.
B.- B._ a recouru contre cette décision devant
la Commission fédérale de recours en matière d'AVS/AI pour
les personnes résidant à l'étranger, en demandant à être
rétabli dans ses droits. Déclarant qu'il n'avait cessé de
réclamer le remboursement des cotisations depuis 1980, il
produisit des lettres de l'Ambassade de Suisse à Alger des
7 décembre 1980 et 24 février 1981, ainsi qu'une réponse de
la Caisse suisse de compensation du 2 novembre 1981,
laquelle l'informait que le remboursement des cotisations
n'était pas possible, la condition de la réciprocité
n'étant pas remplie dans le cas de l'Algérie, pays qui
n'avait conclu avec la Suisse aucune convention de sécurité
sociale.
Par jugement du 22 mars 1999, la juridiction de pre-
mière instance a rejeté le recours.
C.- B._ interjette recours de droit administra-
tif contre ce jugement, en concluant à l'annulation de
celui-ci. Il invite le Tribunal fédéral des assurances à
dire qu'il a droit au remboursement des cotisations AVS.
La caisse conclut au rejet du recours.
D.- Conformément à l'ordonnance de la Cour de céans du
15 juillet 1999, B._ a versé l'avance de frais
requise de 800 fr. Il a élu en Suisse un domicile où les
notifications puissent lui être adressées.
Considérant en droit
:
1.- La décision administrative litigieuse, du 11 mai
1998, détermine la contestation. Elle n'a pas pour objet
l'octroi ou le refus de prestations d'assurance. Le Tribu-
nal fédéral des assurances doit dès lors se borner à exami-
ner si le premier juge a violé le droit fédéral, y compris
par l'excès ou par l'abus de son pouvoir d'appréciation, ou
si les faits pertinents ont été constatés d'une manière
manifestement inexacte ou incomplète, ou s'ils ont été
établis au mépris de règles essentielles de procédure
(art. 132 en corrélation avec les art. 104 let. a et b et
105 al. 2 OJ).
2.- C'est le droit applicable durant les années où le
recourant a cotisé à l'AVS - soit l'<ref-law> an-
cien et l'ordonnance sur le remboursement aux étrangers des
cotisations versées à l'assurance-vieillesse et survivants
(OR) du 14 mars 1952 - qui est déterminant, l'assuré, né en
1915, ayant atteint l'âge d'ouverture du droit (théorique)
à une rente de vieillesse en 1980 (par analogie arrêt F. du
28 janvier 1993 [H 26/90]).
a) Selon l'<ref-law> ancien, dans sa teneur
dès l'entrée en vigueur, le 1er janvier 1973, de la 8e ré-
vision de l'AVS, les cotisations payées conformément aux
art. 5, 6, 8 ou 10 LAVS par des étrangers originaires d'un
Etat avec lequel aucune convention n'avait été conclue
pouvaient être, à titre exceptionnel et sous réserve de
réciprocité, remboursées à eux-mêmes ou à leurs survivants,
à moins que ces cotisations n'ouvrent droit à une rente.
Les mêmes cotisations pouvaient aussi être remboursées aux
réfugiés et aux apatrides lorsqu'ils n'avaient pas droit à
une rente. Le Conseil fédéral était chargé de fixer les
autres conditions mises au remboursement et l'étendue de
celui-ci.
L'<ref-law>, dans sa teneur en vigueur à partir du
1er janvier 1973, disposait que les étrangers avec le pays
d'origine desquels aucune convention n'avait été conclue,
ainsi que leurs survivants, pouvaient, sous réserve de ré-
ciprocité, demander le remboursement des cotisations ver-
sées à l'assurance-vieillesse et survivants, conformément
aux dispositions suivantes, si ces cotisations avaient été
payées, au total, pendant une année entière au moins et
n'ouvraient pas droit à une rente (al. 1). Le Département
fédéral de l'intérieur désignait les Etats dont les ressor-
tissants pouvaient prétendre le remboursement des cotisa-
tions conformément aux dispositions garantissant le droit à
la réciprocité (al. 2).
b) La condition de la réciprocité qui figurait dans
ces dispositions doit donc être prise en considération, de
même que le délai de prescription de cinq ans de la créance
en remboursement courant dès l'accomplissement de l'événe-
ment assuré (<ref-law>). A ce propos, il faut préciser que,
selon la jurisprudence et malgré la terminologie légale, il
s'agit d'un délai de péremption et non de prescription
(arrêt non publié G. du 27 juillet 1993, H 313/92).
3.- Il est établi que le recourant avait déposé une
demande de remboursement des cotisations en 1980 déjà. La
décision administrative litigieuse, du 11 mai 1998, est dès
lors motivée de manière erronée, le recourant ayant bel et
bien demandé avant 1985 le remboursement des cotisations
qu'il avait versées à l'AVS jusqu'à l'année 1979.
4.- a) L'<ref-law> nouveau, dans sa teneur
depuis le 1er janvier 1997, date de l'entrée en vigueur de
la 10e révision de l'AVS, dispose que les cotisations
payées conformément aux art. 5, 6, 8, 10 ou 13 LAVS par des
étrangers originaires d'un Etat avec lequel aucune conven-
tion n'a été conclue peuvent être, en cas de domicile à
l'étranger, remboursées à eux-mêmes ou à leurs survivants.
Le Conseil fédéral règle les détails, notamment l'étendue
du remboursement.
Selon la let. h dernière phrase des dispositions fina-
les de la modification du 7 octobre 1994 (10e révision de
l'AVS), l'<ref-law> (nouveau) s'applique aux per-
sonnes dont les cotisations AVS n'ont pas encore été rem-
boursées et dont le droit au remboursement n'est pas encore
prescrit.
b) Le recourant pourrait donc bénéficier de l'art. 18
al. 3 LAVS nouveau à la condition que le droit au rembour-
sement n'eût pas encore été prescrit lors de l'entrée en
vigueur, le 1er janvier 1997, de la 10e révision de l'AVS,
ce qui a échappé tant à l'intimée qu'aux premiers juges qui
se sont fondés uniquement sur l'OR-AVS du 29 novembre 1995
pour rejeter la demande de remboursement.
5.- Dans le cas particulier, le refus opposé au recou-
rant en 1981 ne semble pas l'avoir été sous la forme d'une
décision. Il n'empêche que celui-ci, s'il n'était pas d'ac-
cord avec la communication de l'intimée du 2 novembre 1981,
aurait pu saisir une autorité de recours, notamment pour
discuter la condition de la réciprocité, question de droit
pouvant être soumise au juge (<ref-ruling> consid. 5b). Il
ne l'a toutefois pas fait dans un délai raisonnablement
exigible (cf. <ref-ruling> consid. 2b).
Aussi, faut-il admettre qu'au regard du droit alors en
vigueur (OR du 14 mars 1952), son droit au remboursement
des cotisations litigieuses était périmé avant le 1er jan-
vier 1997, jour de l'entrée en vigueur de l'art. 18 al. 3
LAVS nouveau. Le recours est mal fondé de ce chef.
6.- Il n'en demeure pas moins que le recourant a été
induit en erreur par la caisse intimée, dans la mesure où
celle-ci a clairement laissé entendre qu'un droit au rem-
boursement pourrait lui être reconnu s'il établissait avoir
demandé celui-ci avant 1985. Et c'est bien cette affirma-
tion qui l'a incité à recourir en première instance et, en
partie, devant la Cour de céans. Dans cette mesure, les
frais de la cause et une indemnité de dépens réduite seront
mis à la charge de l'intimée bien que ce soit le recourant
qui succombe (art. 156 al. 3 et 6 et art. 159 al. 3 et 5
OJ).


Par ces motifs, le Tribunal fédéral des assurances
p r o n o n c e
:
I. Le recours est rejeté au sens des motifs.
II. Les frais de justice, d'un montant de 800 fr., sont
mis à la charge de l'intimée.
III. L'avance de frais versée par le recourant, d'un mon-
tant de 800 fr., lui est restituée.
IV. L'intimée versera au recourant la somme de 1000 fr. (y
compris la taxe sur la valeur ajoutée) à titre de dé-
pens pour l'instance fédérale.
V. Le présent arrêt sera communiqué aux parties, à la
Commission fédérale de recours en matière d'assurance-
vieillesse, survivants et invalidité pour les per-
sonnes résidant à l'étranger, et à l'Office fédéral
des assurances sociales.
Lucerne, le 17 février 2000
Au nom du
Tribunal fédéral des assurances
Le Président de la IIIe Chambre :
Le Greffier :