Faits : A. Par ordonnance du 2 novembre 2015, le Ministère public de la République et canton de Genève a levé partiellement le séquestre opéré en mains du Service des pièces à conviction sur les objets (a) nos 15, 16, 29, 33, 34, 41, 46, 48, 63, 73 et 85 selon la liste annexée au rapport de police du 2 mars 2015, ainsi que (b) nos 2 et 3 de l'inventaire n° 4486320141104 du 4 novembre 2014. Il a ordonné leur restitution, pour les premiers, à C._ et, pour les seconds, à D._. En ce qui concerne les objets attribués à C._, le Procureur a également fixé un délai de trente jours aux autres réclamants - A.A._ et B.A._ - dès l'entrée en force de sa décision pour faire valoir leurs droits par la voie civile. B. A la suite du recours formé le 16 novembre 2015 par A.A._ et B.A._ contre cette ordonnance, le Président de la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a, par ordonnance du jour suivant transmise par télécopie, accordé partiellement l'effet suspensif au recours s'agissant des pièces nos 2 et 3 attribuées à D._. Dans cette même écriture, il a également invité les recourants à verser des sûretés d'ici au 30 novembre 2015 et les a avertis qu'à défaut, il ne serait pas entré en matière sur leur recours. Le 3 décembre suivant, le Tribunal fédéral a déclaré le recours intenté le 30 novembre 2015 par A.A._ et B.A._ contre cette ordonnance sur la question de l'effet suspensif irrecevable, faute de préjudice irréparable (cause 1B_418/2015). Le 28 décembre 2015, la Chambre pénale de recours a refusé d'entrer en matière sur le recours du 16 novembre 2015. Elle a considéré que le versement des sûretés intervenu en date du 2 décembre 2015 était tardif. Cette autorité a également rejeté la requête de restitution de délai déposée le 4 décembre 2015 au motif que l'erreur du mandataire relative à l'inscription du délai ne constituait pas un empêchement non fautif. C. Par acte du 27 janvier 2016, A.A._ et B.A._ forment un recours en matière pénale contre cet arrêt, concluant à la recevabilité du mémoire de recours du 16 novembre 2015 déposé devant la Chambre pénale de recours et au renvoi en conséquence de la cause à celle-ci afin qu'elle statue sur le fond. A titre subsidiaire, ils demandent le renvoi de la cause pour nouvelle décision dans le sens des considérants. Les recourants sollicitent l'octroi de mesures superprovisionnelles afin de suspendre le caractère exécutoire de l'ordonnance du Ministère public du 2 novembre 2015, requête admise le 29 janvier 2016. Invitée à se déterminer, l'autorité précédente n'a pas déposé d'observations. Quant au Ministère public, il a conclu au rejet du recours. Le 15 février 2016, les recourants ont persisté dans leurs conclusions.