Sachverhalt: A. Der Grosse Rat des Kantons Basel-Stadt hat am 18. Januar 2006 ein neues Notariatsgesetz (nNotG) beschlossen, welches am 21. Januar 2006 im Kantonsblatt publiziert wurde. Die Referendumsfrist lief am 4. März 2006 unbenützt ab. Am 11. Mai 2006 erteilte das Eidgenössische Justiz- und Polizeidepartement dem Gesetz die Genehmigung gemäss Art. 52 Abs. 3 SchlT ZGB, was die Staatskanzlei des Kantons Basel-Stadt am 17. Mai 2006 im Kantonsblatt publizierte. B. Am 15. März 2006 haben die Notare Dr. Beat Schultheiss und Dr. Peter Eulau gemeinsam staatsrechtliche Beschwerde beim Bundesgericht eingereicht. Sie stellen den Antrag, "es seien in § 7 Absatz 2 des vom Grossen Rat des Kantons Basel-Stadt am 18. Januar 2006 erlassenen Notariatsgesetzes die Bestimmungen über die Unvereinbarkeit des Notariats mit Organfunktionen bei Immobiliengesellschaften, in § 8 Absätze 1 & 2 sowie in § 10 die Bestimmungen über die Altersgrenze, in § 26 der 2. Satz betreffend Anforderungen an Zeugen und in § 56 Absatz 2 der erste Satz aufzuheben". Das Justizdepartement des Kantons Basel-Stadt schloss am 14. Juni 2006 auf Abweisung der Beschwerde, soweit darauf einzutreten sei; eventuell seien "im Falle der Gutheissung die angefochtenen Wörter gemäss den in dieser Vernehmlassung unter Ziff. 2.1 gemachten Präzisierungen aufzuheben". C. In ihrer Replik vom 29. September 2006 haben die Beschwerdeführer die gestellten Anträge bestätigt, wobei sie sich für die von ihnen verlangten Streichungen dem Eventualbegehren des Kantons Basel-Stadt anschlossen. Das Justizdepartement des Kantons Basel-Stadt hielt mit Duplik vom 13. Dezember 2006 an den gestellten Anträgen fest.