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'art. 18 al. 3 LAVS 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'art. 18 al. 3 LAVS 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'art. 1er OR, 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é (art. 7 OR). 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'art. 18 al. 3 LAVS 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'art. 18 al. 3 LAVS (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 (ATF 111 V 305 consid. 5b). Il ne l'a toutefois pas fait dans un délai raisonnablement exigible (cf. ATF 110 V 168 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).