Faits :
A.
En date du 22 janvier 2014, le Service des automobiles et de la navigation du canton de Vaud (SAN) a invité A._, né le 22 mai 1944, à se soumettre à un examen médical, joignant le questionnaire à faire remplir par le médecin traitant; ce courrier, adressé à la rue xxx, à 1530 Payerne, a été retourné à son expéditeur avec la mention "la boîte aux lettres/la case n'a plus été vidée". Une lettre identique a été envoyée le 11 février 2014 à cette même adresse et retournée avec les mêmes indications que la première. Le SAN a sollicité, par courrier du 17 février 2014, A._ de prendre contact le plus rapidement possible par téléphone avec la personne en charge de son dossier. Par lettre du 2 juillet 2014, le SAN a constaté que A._ n'avait pas apporté la preuve de son aptitude à la conduite dans le délai imparti et, par conséquent, une mesure de retrait du permis de conduire était envisagée. Sans réponse, le SAN a prononcé, le 18 juillet 2014, le retrait de sécurité du permis de conduire de A._, décision adressée à ce dernier par pli recommandé à l'adresse payernoise susmentionnée; ce courrier est revenu en retour au SAN le 11 août 2014 avec la mention indiquée ci-dessus.
Le 11 septembre 2014, le SAN a rendu une nouvelle décision de retrait du permis de conduire au contenu similaire à la précédente et a fixé, à la charge de l'intéressé, les frais de procédure (200 fr.); ce courrier - envoyé par pli recommandé - a été retourné à son expéditeur le 15 septembre 2014 avec la même indication que les précédents envois. Le dispositif de cette décision a été publié dans la Feuille des avis officiels (FAO) du 7 octobre 2014.
Une facture de fr. 200 a été adressée à A._ par le SAN le 1er septembre 2014; des rappels ont été envoyés les 17 juin et 13 juillet 2015. Le 13 octobre suivant, le SAN a fait adresser, par le biais de l'Office des poursuites du district de la Broye-Vully, un commandement de payer à A._, acte notifié à la Prison centrale de Fribourg où ce dernier était incarcéré; l'intéressé a formé opposition. Le 6 novembre 2015, le SAN a invité A._ à s'acquitter de 233 fr. 30, montant comprenant les frais de procédure et de poursuite; ce courrier a été adressé au lieu de détention de l'intéressé. Celui-ci a formé recours contre cette décision, alléguant n'avoir reçu aucun des courriers du SAN, notamment en raison de son placement en détention depuis le 21 août 2013.
B.
Par arrêt du 4 avril 2016, la Cour de droit administratif et public du Tribunal cantonal vaudois a rejeté ce recours. Elle a considéré que la décision du 11 septembre 2014 avait été valablement notifiée par voie édictale. L'autorité précédente a ensuite relevé que, vu l'absence de contestation en temps utile du retrait du permis de conduire ainsi que de la fixation à la charge de l'intéressé des frais de procédure, cette décision était entrée en force et, partant, elle ne pouvait plus être contestée.
C.
Le 18 avril 2016, A._ forme un recours au Tribunal fédéral contre cet arrêt et sollicite l'octroi de l'assistance judiciaire. Par mémoire du 6 mai 2016, Me Nader Ghosn, agissant au nom du recourant, a complété cette écriture, demandant l'annulation de l'arrêt du 4 avril 2016, la constatation de la nullité de la décision du SAN relative au retrait de sécurité du permis de conduire, son annulation, ainsi que celle de la décision de paiement du 6 novembre 2015; il a encore sollicité la reprise de la procédure d'examen de l'aptitude à la conduite et la fixation d'un délai approprié au recourant.
Le SAN et l'autorité précédente ont conclu au rejet du recours; le premier a toutefois produit une copie des données qu'il peut consulter sur le Registre cantonal des personnes. Le 4 juillet 2016, le recourant a persisté dans ses conclusions, joignant notamment à ses déterminations une copie du questionnaire médical du SAN dûment complété le 2 juin 2016 par le docteur B._.
Par ordonnance du 21 avril 2016, le Président de la Ire Cour de droit public a octroyé l'assistance judiciaire au recourant et a désigné Me Nader Ghosn en qualité de défenseur d'office.

Considérant en droit :
1.
La voie du recours en matière de droit public, au sens des <ref-law>, est en principe ouverte contre une décision prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) au sujet d'une mesure administrative de retrait du permis de conduire (<ref-law>), aucune des exceptions mentionnées à l'<ref-law> n'étant réalisée.
Soutenant n'avoir notamment pas reçu la décision du 11 septembre 2014 et contestant en conséquence en substance la mesure prononcée à son encontre et les frais mis à sa charge, le recourant peut se prévaloir d'un intérêt digne de protection à l'annulation ou à la modification de l'arrêt attaqué (<ref-law>); celui-ci confirme en effet la validité de la notification du prononcé susmentionné et les frais (233 fr. 30) mis à la charge du recourant dans la décision du 6 novembre 2015 à l'origine du présent litige.
Les autres conditions de recevabilité, dont le dépôt en temps utile du complément au recours, sont au surplus réunies, de sorte qu'il convient d'entrer en matière.
2.
Le recourant reproche à l'autorité précédente d'avoir considéré que la décision du 11 septembre 2014 lui aurait été notifiée valablement. En particulier, il soutient que les conditions permettant la notification par voie édictale au sens de l'art. 44 al. 3 let. a de la loi cantonale du 28 octobre 2008 sur la procédure administrative (LPA-VD; RSV 173.36) ne seraient pas réunies, faute de lieu de séjour inconnu. Le recourant se plaint encore que le SAN n'aurait entrepris aucune démarche pour le localiser et prétend qu'il ne lui appartiendrait pas de subir les conséquences des éventuelles erreurs que comporterait le Registre cantonal des personnes sur lequel se serait fondé le SAN.
2.1. Selon l'<ref-law>, l'autorité cantonale convoque tous les deux ans les titulaires âgés de 70 ans et plus à l'examen d'un médecin-conseil; elle peut réduire l'intervalle entre deux examens si l'aptitude à la conduite est altérée et doit donc être contrôlée plus fréquemment (cf. également l'art. 27 al. 2 de l'ordonnance réglant l'admission des personnes et des véhicules à la circulation routière [OAC; RS 741.51]). Les permis et les autorisations seront retirés lorsque l'autorité constate que les conditions légales de leur délivrance ne sont pas ou ne sont plus remplies; ils pourront être retirés lorsque les restrictions ou les obligations imposées dans un cas particulier, lors de la délivrance, n'auront pas été observées (<ref-law>).
En matière de retrait du permis de conduire, la procédure de première instance est de la compétence des cantons, sous réserve des exigences minimales prévues par l'<ref-law>. Cette disposition prévoit que le retrait d'un permis de conduire doit être notifié par écrit, avec indication des motifs.
De jurisprudence constante, celui qui se sait partie à une procédure administrative ou judiciaire et qui doit dès lors s'attendre, selon une certaine vraisemblance, à recevoir des actes de l'autorité, est tenu de relever son courrier ou, s'il s'absente de son domicile, de prendre des dispositions pour que celui-ci lui parvienne néanmoins. Une telle obligation signifie que le destinataire doit, le cas échéant, désigner un représentant, faire suivre son courrier, informer les autorités de son absence ou leur indiquer une adresse de notification (<ref-ruling> consid. 3.1 p. 431 s.; <ref-ruling> consid. 1.1 p. 230 et les références citées). Ce devoir procédural ne naît toutefois qu'avec l'ouverture d'un procès et vaut pendant toute la durée de la procédure (<ref-ruling> consid. 3.1 p. 227 s.; <ref-ruling> consid. 1.2.3 p. 399 s.).
2.2. La cour cantonale a retenu qu'au vu de la loi et de son âge (70 ans le 22 mai 2014), le recourant devait s'attendre avec une certaine prévisibilité à recevoir un courrier du SAN en vue de déterminer son aptitude à la conduite. Selon l'autorité précédente, il appartenait donc en substance au recourant de prendre les mesures nécessaires pour relever son courrier; dès lors que tel n'avait pas été le cas et que son lieu de séjour était inconnu, le SAN était en droit de notifier par voie édictale la décision du 11 septembre 2014.
Ce raisonnement ne peut être suivi. Certes, selon le principe général, nul n'est censé ignorer la loi (arrêts 2C_951/2014 du 16 avril 2015 consid. 3.1.1; 2A.439/2003 du 2 février 2004 consid. 9.2; MOOR/FLÜCKIGER/MARTENET, Droit administratif, vol. I, Les fondements, 3ème éd. 2012, ad 2.4.2.1/c p. 183) et un conducteur approchant l'âge visé par l'<ref-law> peut donc s'attendre à recevoir une convocation en vue de l'examen prescrit. Cependant, la seule perspective de l'ouverture d'une procédure - à une date par ailleurs inconnue - ne peut s'apparenter à la situation où une procédure administrative ou judiciaire est déjà pendante au sens des principes rappelés ci-dessus. A teneur claire de la loi, l'initiative de l'ouverture formelle de la procédure au sens de l'<ref-law> incombe en outre à l'autorité et non pas au recourant. Il ne pouvait donc être attendu de ce dernier qu'il prenne les mesures nécessaires pour assurer le suivi de son courrier à la suite de son placement en détention provisoire en vue de la réception d'un hypothétique courrier du SAN. Admettre dans cette hypothèse un tel devoir viole l'interdiction du formalisme excessif (sur cette notion, <ref-ruling> consid. 4.2 p. 158 et les arrêts cités en lien avec l'art. 29 Cst.) et le principe de la bonne foi (cf. <ref-ruling> consid. 8.3.1 p. 53), eu égard en particulier aux éventuelles conséquences importantes pouvant découler d'une fiction de notification. Partant, la décision du 11 septembre 2014 n'a pas été notifiée régulièrement au recourant et ce grief doit donc être admis.
2.3. Malgré l'absence de notification, la décision du 11 septembre 2014 n'est pas nulle, mais elle est inopposable à son destinataire (<ref-ruling> consid. 3.1.1 p. 187; arrêt 8C_130/2014 du 22 janvier 2015 consid. 2.3.2 et les références citées publié in SJ 2015 I 293; MOOR/POLTIER, Droit administratif, vol. II, Les actes administratifs et leur contrôle, 3ème éd. 2011, n° 2.2.8.5 p. 356 et n° 2.3.4.4 p. 374), cela sous réserve des règles de la bonne foi (<ref-ruling> consid. 6 p. 253; <ref-ruling> consid. 3a/aa p. 99; arrêts 8C_664/2015 du 13 juin 2016 consid. 3; 8C_130/2014 du 22 janvier 2015 consid. 2.3.2 et les références citées). Il apparaît en l'espèce que le comportement adopté par le recourant ne viole pas ce principe. Il a en effet réagi en temps utile dès qu'il a eu connaissance des communications en lien avec le prononcé du 11 septembre 2014 : il a ainsi formé opposition au commandement de payer et a déposé un recours contre la décision du 6 novembre 2015 du SAN. Le défaut de notification n'est pas non plus dénué de conséquences pour le recourant - certes détenu - qui se trouve privé de son permis de conduire et est condamné à payer les frais de procédure, puis ceux de recouvrement en vertu de la décision du 6 novembre 2015.
Il appartiendra donc au SAN de procéder à une notification conforme de sa décision; dans cette intervalle, il est d'ailleurs relevé que celui-ci n'est pas non plus lié par le contenu de son prononcé, pouvant, le cas échéant, donc librement le modifier (MOOR/POLTIER, op. cit., n° 2.2.8.5 p. 356), eu égard notamment au questionnaire médical que le recourant a fait établir.
3.
Il s'ensuit que le recours est admis. L'arrêt de la Cour de droit administratif et public du 4 avril 2016 est annulé. La cause est renvoyée au SAN pour qu'il procède au sens des considérants.
Le recourant bénéficie de l'assistance judiciaire. Il obtient cependant gain de cause avec l'assistance d'un avocat et a donc droit à des dépens à la charge du canton de Vaud (<ref-law>). Il n'est pas perçu de frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. L'arrêt de la Cour de droit administratif et public du Tribunal cantonal vaudois du 4 avril 2016 est annulé et la cause est renvoyée au Service des automobiles et de la navigation pour qu'il procède au sens des considérants.
2.
Une indemnité de dépens de 2'000 fr. est allouée au mandataire du recourant à la charge du canton de Vaud.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Service des automobiles et de la navigation du canton de Vaud et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud.
Lausanne, le 24 août 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Kropf