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 <ref-law>, 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.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Auf das vorliegende Verfahren findet noch das bis Ende 2006 geltende Bundesgesetz vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG) Anwendung (vgl. Art. 132 Abs. 1 des am 1. Januar 2007 in Kraft getretenen Bundesgesetzes vom 17. Juni 2005 über das Bundesgericht [BGG; SR 173.110]).
1.2 Mangels der Möglichkeit einer abstrakten Normenkontrolle kann der streitige Erlass im Kanton Basel-Stadt nicht angefochten werden und stellt deshalb einen letztinstanzlichen kantonalen Hoheitsakt im Sinne von Art. 86 Abs. 1 OG dar. Auf Bundesebene kommt als Rechtsmittel allein die hier ergriffene staatsrechtliche Beschwerde in Frage (Art. 84 Abs. 2 OG). Bei den Beschwerdeführern handelt es sich um im Kanton Basel-Stadt praktizierende Notare (und Advokaten), so dass sie - soweit sie durch die angefochtenen Normen direkt oder virtuell in rechtlich geschützten Interessen berührt werden - zur staatsrechtlichen Beschwerde legitimiert sind (vgl. Art. 87 OG).
1.3 Die dreissigtägige Beschwerdefrist zur Anfechtung des kantonalen Erlasses (vgl. Art. 89 Abs. 1 OG) ist eingehalten worden: Für die Fristauslösung massgebend war vorliegend die Publikation des - konstitutiven (vgl. Art. 61b des Regierungs- und Verwaltungsorganisationsgesetzes des Bundes vom 21. März 1997 [RVOG; SR 172.010] in Verbindung mit <ref-law>) - Genehmigungsentscheids des Eidgenössischen Justiz- und Polizeidepartements am 17. Mai 2006 (vgl. <ref-ruling> E. 1a/b S. 189). Zwar haben die Beschwerdeführer ihre staatsrechtliche Beschwerde schon vor diesem Datum eingereicht, was indessen nicht schadet.
2. 2.1 Obschon der materielle Begriff der öffentlichen Beurkundung dem Bundesrecht angehört, liegt die Kompetenz zu deren gesetzlichen Regelung grundsätzlich bei den Kantonen. Diesen wird durch <ref-law> die Aufgabe übertragen, zu bestimmen, wer auf dem Kantonsgebiet zur Errichtung öffentlicher Urkunden befugt und wie dabei vorzugehen ist. Neben Zuständigkeit und Form des Verfahrens sind insbesondere die Voraussetzungen für die Tätigkeit als Urkundsperson, die Aufgaben und Berufspflichten der Urkundspersonen sowie das Gebühren- und Aufsichtswesen zu regeln (<ref-ruling> E. 6.1 S. 645; vgl. auch Louis Carlen, Notariatsrecht der Schweiz, Zürich 1976, S. 35; Christian Brückner, Schweizerisches Beurkundungsrecht, Zürich 1993, S. 3 f. N 5; Peter Ruf, Notariatsrecht, Langenthal 1995, S. 34 N 130 u. S. 37 N 140).
2.2 Diese Normierungsfreiheit der Kantone wird immerhin in zweierlei Hinsicht beschränkt, einerseits durch die bundesrechtlichen Mindestanforderungen, die sich aus dem materiellrechtlichen Zweck des Instituts ergeben (<ref-ruling> E. 1 S. 147; zu deren Umfang vgl. Ruf, a.a.O., S. 46 ff. N 162-164), und andererseits durch die punktuellen Regelungen, welche die Beurkundungsgeschäfte im Gesetzesrecht des Bundes erfahren (vgl. hierzu Hans Marti, Notariatsprozess, Bern 1989, S. 35 f.). Keinerlei Einschränkung durch das Bundesrecht erfährt die kantonale Gesetzgebungskompetenz jedoch bezüglich der Zulassung der Notare zur Berufsausübung. In der Ausgestaltung der entsprechenden Regelung sind die Kantone deshalb weitgehend frei (<ref-ruling> E. 7.3 S. 646 f.), zumal die Notare aufgrund der ihnen verliehenen Beurkundungsbefugnis Träger einer hoheitlichen Funktion sind und sich - weil sie an der Staatsgewalt teilhaben - nicht auf die Wirtschaftsfreiheit gemäss <ref-law> berufen können (<ref-ruling> E. 6.1 S. 645; <ref-ruling> E. 3 S. 281 f.; vgl. auch Carlen, a.a.O., S. 37; Brückner, a.a.O., S. 152 N 481 und S. 153 N 485 ff.; Ruf, a.a.O., S. 74 f. N 251). Dementsprechend behalten verschiedene Kantone das Beurkundungswesen Beamten vor, indem sie dieses durch die Schaffung des Amtsnotariats gänzlich dem wirtschaftlichen Wettbewerb entziehen. Andere haben Höchst- oder Mindestgrenzen für die Zahl der (freien) Notare festgelegt, wodurch sie lenkend auf die Anzahl der praktizierenden Urkundspersonen Einfluss nehmen (vgl. Carlen, a.a.O., S. 36 ff.).
2.3 Das neue Notariatsgesetz des Kantons Basel-Stadt kennt das freie Notariat: Die Notare sind auf dem Kantonsgebiet für die Beurkundung aller Geschäfte und Tatsachen zuständig, welche von Gesetzes wegen oder nach dem Willen der Parteien in Form einer öffentlichen Urkunde festzuhalten sind (§ 2 nNotG). Zur Erlangung des beruflichen Fähigkeitsausweises haben die Bewerber eine Prüfung zu bestehen (§ 3 ff. nNotG), während die Erteilung der Beurkundungsbefugnis anschliessend von zusätzlichen persönlichen Voraussetzungen abhängig ist (vgl. § 7 nNotG). Insbesondere wird die "berufliche Selbständigkeit" des Notars verlangt, wobei § 7 Abs. 2 nNotG näher regelt, was unter diesem Begriff zu verstehen ist.
3. 3.1 Die vorliegende staatsrechtliche Beschwerde richtet sich unter anderem gegen diese Umschreibung der beruflichen Selbständigkeit, nämlich gegen die vorgesehene Unvereinbarkeit von Beurkundungsbefugnis und Organstellung bei einer Immobiliengesellschaft. Der Gesetzestext von § 7 Abs. 2 nNotG lautet wie folgt:
"Als beruflich selbständig gilt, wer als selbständigerwerbende Notarin oder als selbständigerwerbender Notar tätig oder bei einer Notarin oder einem Notar angestellt ist. Die Anstellung bei anderen Unternehmungen ist mit der Beurkundungsbefugnis unvereinbar, desgleichen die Ausübung von Handels- und Vermittlungstätigkeiten im Liegenschaftsbereich und die Ausübung von Organfunktionen oder die anderweitige Kontrolle von Unternehmungen, deren Zweck oder Haupttätigkeit der Handel mit Liegenschaften ist. Die Justizkommission kann Ausnahmen bewilligen für Anstellungsverhältnisse, die aufgrund ihres geringen zeitlichen Umfangs und der Art der Beanspruchung die notarielle Unabhängigkeit nicht beeinträchtigen können."
Nachdem die Beschwerdeführer ihren Antrag entsprechend dem Eventualbegehren des Justizdepartements des Kantons Basel-Stadt präzisiert haben, wird vorliegend die Streichung des letzten Teils des zweiten Satzes von § 7 Abs. 2 nNotG verlangt ("...und die Ausübung von Organfunktionen oder die anderweitige Kontrolle von Unternehmungen, deren Zweck oder Haupttätigkeit der Handel mit Liegenschaften ist"). Zur Begründung tragen die Beschwerdeführer vor, die Ausstandsvorschriften des neuen Notariatsgesetzes (vgl. § 23 ff.) seien ausreichend, um Interessenkollisionen bei den Notaren auszuschliessen. Es sei deshalb überflüssig, gesetzlich eine generelle Unvereinbarkeit der Beurkundungsbefugnis mit der Organstellung bei einer Immobiliengesellschaft vorzusehen. Für die streitige Regelung fehle jeglicher sachliche Grund, weshalb sie gegen das Willkürverbot von <ref-law> (vgl. <ref-ruling> E. 5a S. 70) verstosse.
3.2 Das Justizdepartement führt demgegenüber aus, die Rechtsuchenden seien nicht frei in ihrem Entschluss, die Dienstleistungen einer Urkundsperson in Anspruch zu nehmen. Im Rahmen der beurkundungspflichtigen Rechtsgeschäfte bestehe ein staatlicher Zwang, dem Notar Geheimnisse anzuvertrauen. Deshalb müsse verhindert werden, dass dieser privaten Nutzen aus den anvertrauten Informationen ziehen könne. Das gelte besonders für das Marktgeschehen im Bereich des Immobilienhandels, so dass die streitige Bestimmung sachlich gerechtfertig sei.
3.3 Entgegen der Auffassung der Beschwerdeführer erscheint die Unvereinbarkeitsbestimmung ohne weiteres als haltbar: Gemäss Lehre und Rechtsprechung ist die Unabhängigkeit und Neutralität des freiberuflich tätigen Notars von herausragender Bedeutung. Mit Blick hierauf hat das Bundesgericht eine Regelung des Kantons Genf für verfassungsmässig erklärt, welche den dortigen Notaren (fast) alle Formen von Nebenerwerbstätigkeiten verbietet (Urteil 2P.62/1989, in: SJ 1990 S. 97). Es hat diesbezüglich erwogen, jegliche Beteiligung am Wirtschaftsleben führe zu einer gewissen Gefährdung der Unabhängigkeit des Notars. Es sei deshalb Sache des kantonalen Gesetzgebers, abzuwägen, in welchem Ausmass er Nebenbeschäftigungen seiner Notare gestatten oder deren Neutralität absichern wolle (vgl. auch Urteil 2P.151/1995, in: RDAT 1997 II 14, E. 3c; Urteil 2P.226/2006 vom 8. Dezember 2006, E. 4.2). Abgesehen von den unselbständigen Nebenerwerbstätigkeiten hat der Kanton Basel-Stadt seinen Urkundspersonen im Wesentlichen bloss die Beteiligung am Liegenschaftenhandel untersagt, so dass es sich bei § 7 Abs. 2 nNotG keinesfalls um eine restriktive Bestimmung handelt: Der (gewerbsmässige) Liegenschaftenhandel wird gemeinhin als mit dem Ansehen des Notariatsberufs unvereinbar betrachtet (vgl. Ruf, a.a.O., S. 123 N 448; Brückner, a.a.O., S. 982 N 3482; Carlen, a.a.O., S. 64). Dies scheinen auch die Beschwerdeführer nicht zu verkennen, zumal sie gegen die in § 7 Abs. 2 nNotG vorgesehene Unvereinbarkeit von Beurkundungsbefugnis und "Handels- und Vermittlungstätigkeiten im Liegenschaftsbereich" nichts einzuwenden haben. Dabei übersehen sie aber, dass sich eine Beteiligung am Liegenschaftenhandel als Organ einer Immobiliengesellschaft letztlich nicht von einer selbständigen Betätigung des Notars als Liegenschaftenhändler unterscheidet. Nach dem Gesagten kann hier jedenfalls zum Vornherein nicht von einer unsachlichen und willkürlichen Beschränkung der beruflichen Entfaltungsmöglichkeiten der Basler Notare die Rede sein. Mithin kann offen bleiben, ob auch eine Regelung denkbar wäre, gemäss welcher der Notar die Erstellung der Urkunde immer nur dann einem Berufskollegen zu überlassen hätte, wenn er sich als Organ einer Immobiliengesellschaft bezüglich des konkreten Geschäfts tatsächlich in einem Interessenkonflikt befinden würde.
3.4 Nichts zugunsten der Beschwerdeführer lässt sich schliesslich aus dem Umstand ableiten, dass ein Rechtsanwalt, welcher die Interessen von Immobiliengesellschaften vertritt, dabei teilweise die gleichen Geheimnisse erfahren kann wie der Notar anlässlich einer Verurkundung von Rechtsgeschäften. Zum einen ist die Stellung des Rechtsanwalts - auch wenn dieser eine gewisse Mitverantwortung für das korrekte Funktionieren des Rechtsstaats trägt (vgl. <ref-ruling> E. 3.2.2 S. 277) und besonderen (bundesrechtlichen) Berufsregeln untersteht (vgl. Art. 12 des Bundesgesetzes vom 23. Juni 2000 über die Freizügigkeit der Anwältinnen und Anwälte [BGFA; SR 935.61]) - nicht mit jener eines Notars zu vergleichen, welcher an der Staatsgewalt als solcher teilhat. Zum anderen untersagt § 7 Abs. 2 nNotG dem Notar nur die aktive (eigennützige) Teilnahme am Liegenschaftenhandel, so dass er, gleich wie ein Rechtsanwalt, Beratungsmandate von Immobiliengesellschaften grundsätzlich annehmen darf. Schliesslich versteht sich von selbst, dass jene Notare, welche gleichzeitig als Rechtsanwalt tätig sind, ohne weiteres auch als solche gehalten sind, die einschlägigen Unvereinbarkeitsbestimmungen des Notariatsrechts zu respektieren.
4. Das neue Notariatsgesetz sieht - der bisherigen (auf keiner gesetzlichen Grundlage beruhenden) kantonalen Praxis entsprechend - ein Höchstalter für Notare vor, ab dessen Erreichen der Regierungsrat die Beurkundungsbefugnis nicht mehr verlängert; gemäss § 8 Abs. 1 nNotG liegt diese Altersgrenze bei 75 Jahren (anstatt wie bis anhin bei 80 Jahren). Die Beschwerdeführer rügen insoweit eine Verletzung des Willkürverbots (<ref-law>) und verlangen die teilweise Aufhebung sowohl der Absätze 1 und 2 von § 8 als auch von § 10 nNotG.
4.1 § 8 nNotG hat folgenden Wortlaut:
"1Das Gesuch um Verleihung der Beurkundungsbefugnis ist an die Justizkommission zuhanden des Regierungsrates zu stellen. Der Regierungsrat verleiht die Beurkundungsbefugnis auf Antrag der Justizkommission in der Regel auf die Dauer von sechs Jahren und erneuert sie vor Ablauf der Amtszeit ohne weiteres, längstens jedoch bis zum Erreichen des 75. Altersjahrs der Notarin oder des Notars. Ist die Ablehnung des Gesuchs oder die Nichterneuerung der Amtsdauer aus einem anderen Grund als demjenigen der Altersgrenze beabsichtigt, so ist die Notarin oder der Notar anzuhören.
2Die Ablehnung des Gesuchs sowie die Nichterneuerung der Amtsdauer aus einem anderen Grund als demjenigen der Altersgrenze unterliegt dem Rekurs an das Verwaltungsgericht.
3 [...]"
Nachdem die Beschwerdeführer ihren Antrag entsprechend dem Eventualbegehren des Justizdepartements des Kantons Basel-Stadt präzisiert haben, wird zum einen in § 8 Abs. 1 die Streichung des letzten Teils von Satz 2 ("...längstens jedoch bis zum Erreichen des 75. Altersjahrs der Notarin oder des Notars") verlangt. Zum anderen wird - sowohl in Satz 3 von § 8 Abs. 1 als auch in § 8 Abs. 2 - die Streichung des Passus "...aus einem anderen Grund als demjenigen der Altersgrenze..." beantragt.
Während § 8 die Verleihung der Beurkundungsbefugnis regelt, betrifft § 10 nNotG deren Erlöschen:
"Die Beurkundungsbefugnis erlischt durch schriftliche Verzichtserklärung, Erreichen der gesetzlichen Altersgrenze, Tod, Nichterneuerung der Amtsdauer, Konkurseröffnung, Ausstellung von Verlustscheinen und Entzug."
Entsprechend dem Eventualbegehren des Justizdepartements des Kantons Basel-Stadt wird insoweit die Löschung der Worte "Erreichen der gesetzlichen Altersgrenze" beantragt.
4.2 Vor einiger Zeit hatte das Bundesgericht eine ähnliche Regelung zu überprüfen, mit welcher der Kanton Neuenburg für seine (freien) Notare die Altersgrenze von 70 Jahren einführte (<ref-ruling>). Das Bundesgericht erwog, die körperlichen und geistigen Fähigkeiten der Menschen nähmen im Alter ab, so dass für jeden Notar der Zeitpunkt komme, ab dem er gesundheitsbedingt nicht mehr Gewähr für eine tadellose Ausübung der ihm übertragenen Funktion bieten könne. Obschon sich dieser Moment durch eine periodische Überprüfung des körperlichen und geistigen Gesundheitszustands für jeden betagten Notar individuell bestimmen liesse, erachtete das Bundesgericht die Einführung einer einheitlichen Altersgrenze für alle praktizierenden Notare als zulässig. Es entschied weiter, die vom Kanton Neuenburg gewählte Altersgrenze von 70 Jahren lasse den Notaren genügend Zeit, ihren Ruhestand finanziell abzusichern. Auch mit Blick auf das Pensionierungsalter von Schweizer Beamten und Magistraten, welches gemeinhin im Bereich von 65 bis maximal 70 Jahren liegt, erwies sich die Altersgrenze als mit dem Rechtsgleichheitsgebot und dem Willkürverbot vereinbar (E. 4c/d S. 301 ff.). An dieser Rechtsprechung ist vorliegend ohne Einschränkungen festzuhalten, weshalb die - mit 75 Jahren höhere - Altersgrenze für basel-städtische Notare verfassungsrechtlich nicht zu beanstanden ist.
4.3 Im Übrigen gehen die Vorbringen der Beschwerdeführer ohnehin an der Sache vorbei: Eine Regelung verstösst nur dann gegen das Willkürverbot, wenn sie sich nicht auf ernsthafte sachliche Gründe stützen lässt oder sinn- und zwecklos ist (<ref-ruling> E. 3 S. 3). Deshalb ist unerheblich, ob - angesichts einer relativ geringen Anzahl von älteren in der Stadt Basel praktizierenden Notaren - die Entwicklung von deren beruflichen Fähigkeiten mit mehr oder weniger Aufwand individuell überwacht werden könnte. Selbst wenn feststehen würde, dass ein derartiges System zu einer besseren Verwirklichung jener Ziele führen würde, welche mit der streitigen Altersgrenze verfolgt werden, wäre die Verfassungswidrigkeit der Altersgrenze damit noch nicht dargetan, zumal Letztere nach dem Gesagten weder sinn- noch zwecklos ist. Geradezu abwegig erscheint weiter der Vorschlag, der Staat könnte und müsste betagten Notaren die Beurkundungsbefugnis erst dann entziehen, wenn diese nachweislich mangelhafte Urkunden hergestellt hätten. Ein entsprechendes Zuwarten des Kantons, bis sich seine Notare derart gravierende Fehler leisten, dass auf ihre Berufsunfähigkeit geschlossen werden muss, würde zu inakzeptablen Risiken für das Publikum und für die Rechtssicherheit führen (vgl. <ref-ruling> E. 4c S. 301); ob allenfalls die Berufshaftpflichtversicherung des betroffenen Notars für verursachte Schäden einzustehen hätte, ist in diesem Zusammenhang unerheblich.
4.4 Schliesslich ist auf die Beschwerde nicht einzutreten, soweit im vorliegenden Zusammenhang auch eine Verletzung von <ref-law> gerügt wird (vgl. E. 2.2): Zwar stehen Rechtsanwälte anders als Urkundspersonen im Genuss der Wirtschaftsfreiheit (vgl. etwa <ref-ruling> E. 7.1 S. 205); die Beschwerdeführer können sich jedoch auch als Advokaten nicht auf dieses Freiheitsrecht berufen, wenn sie daraus mittelbar etwas für ihre Tätigkeit als Notare des Kantons Basel-Stadt ableiten wollen.
5. Für letztwillige Verfügungen, welche unter anderem in die Form einer öffentlichen Urkunde gekleidet werden können (<ref-law>), hat der Bundesgesetzgeber materielle Bestimmungen über die Art und Weise der Verurkundung erlassen. Verlangt wird insbesondere die Mitwirkung zweier Zeugen (<ref-law>), welche gewissen persönlichen Voraussetzungen zu genügen haben: Gemäss <ref-law> müssen sie handlungsfähig sein sowie lesen und schreiben können; nicht als Zeugen zugelassen sind neben dem überlebenden Ehegatten auch die Geschwister des Erblassers und dessen Verwandte in gerader Linie sowie die Ehegatten der Genannten.
5.1 Angefochten ist vorliegend § 26 nNotG, welcher die bundesrechtliche Zeugenregelung für den Kanton Basel-Stadt wie folgt konkretisiert:
"Zeuginnen und Zeugen der Beurkundung müssen die Anforderungen von <ref-law> erfüllen und dürfen der Notarin oder dem Notar nicht im Sinne von § 25 Abs. 1 nahestehen. Sie dürfen nicht Mitarbeitende des gleichen Büros sein."
Die Beschwerdeführer beantragen die Aufhebung von Satz 2 dieser Bestimmung. Zur Begründung führen sie aus, die bundesrechtliche Regelung zur Unabhängigkeit der Zeugen sei abschliessender Natur, weshalb der in § 26 Satz 2 nNotG vorgesehene Ausschluss von Zeugen, welche im gleichen Büro wie der beurkundende Notar tätig seien, den Vorrang des Bundesrechts (<ref-law>) verletze. Die Beschwerdeführer machen weiter geltend, die fragliche Regelung verletze sowohl das Willkürverbot (<ref-law>) als auch das Rechtsgleichheitsgebot (<ref-law>). Weil diese letzteren Verfassungsrügen den gesetzlichen Begründungsanforderungen von Art. 90 Abs. 1 lit. b OG (vgl. <ref-ruling> E. 2 S. 3 f.; <ref-ruling> E. 1d S. 201) offensichtlich nicht zu genügen vermögen, ist auf diese Vorbringen jedoch nicht weiter einzugehen.
5.2 Die Einhaltung jener Formvorschriften, welche das Bundesrecht für öffentlich beurkundete letztwillige Verfügungen statuiert, stellt ein Gültigkeitserfordernis dar (Peter Tuor, in: Berner Kommentar, N 4 ff. vor <ref-law>; Arnold Escher, in: Zürcher Kommentar, N 5 vor <ref-law>; Peter Breitschmid, in: Basler Kommentar zum Schweizerischen Privatrecht, Zivilgesetzbuch II, 2. Auflage, Basel/ Genf/ München 2003, N 8 zu <ref-law>), so dass ein Formverstoss grundsätzlich zur Ungültigkeit des betroffenen Testaments führt. Den Beschwerdeführern ist insoweit zuzustimmen, als diese Regelung des Bundeszivilrechts abschliessender Natur ist (Breitschmid, a.a.O., N 16 zu <ref-law>; vgl. auch Ruf, a.a.O., S. 348 N 1321 u. S. 202 N 739), weshalb der kantonale Gesetzgeber keine zusätzlichen Gültigkeitsvorschriften erlassen kann. Dies bedeutet jedoch nicht, dass es den Kantonen untersagt wäre, im Rahmen ihrer Kompetenz zur Regelung der öffentlichen Beurkundung (vgl. E. 2) weitere Ausschliessungsgründe für Zeugen vorzusehen. Solche zusätzlichen kantonalen "Unfähigkeitsgründe" stellen gegebenenfalls blosse Ordnungsvorschriften dar (Tuor, a.a.O., N 2 zu <ref-law>; Escher, a.a.O., N 2 zu Art. 503 u. N 7 vor <ref-law>), deren Missachtung lediglich von disziplinarrechtlicher Bedeutung ist und die Gültigkeit der Urkunde nicht zu beeinträchtigen vermag. Um eine derartige dem autonomen kantonalen Beurkundungsrecht zugehörige Ordnungsvorschrift handelt es sich beim hier streitigen § 26 Satz 2 nNotG. Diese Bestimmung soll als Unabhängigkeitsregel im Verhältnis zwischen Notar und Zeugen dazu beitragen, dass Letztere die ihnen gemäss einem Teil der Lehre zukommende Kontrollfunktion besser wahrnehmen können (vgl. hierzu Brückner, a.a.O., S. 131 f. N 391 ff.; anderer Meinung sind die Berner Autoren, welche die Zeugen als blosse Hilfspersonen des Notars betrachten, die keiner Unabhängigkeit bedürfen: vgl. Ruf, a.a.O., S. 348 f. N 1321 ff.; Daniel Santschi, Die Ausstandspflicht des Notars, Langenthal 1992, S. 57 f. N 167 ff.; vgl. auch Marti, a.a.O., S. 70 f.). Dementsprechend gehen weder der Kanton Basel-Stadt (vgl. § 55 nNotG) noch das Eidgenössische Polizei- und Justizdepartement (vgl. dessen Genehmigungsverfügung vom 11. Mai 2006) davon aus, dass ein Verstoss gegen § 26 Satz 2 nNotG bei der betroffenen Urkunde zu einem Mangel führen würde. Es liegt daher - ungeachtet der hinsichtlich der formellen Gültigkeitserfordernisse abschliessenden Natur der Regelung des Bundeszivilrechts - kein Verstoss gegen den Vorrang des Bundesrechts vor.
6. 6.1 Die Notare des Kantons Basel-Stadt sind gehalten, die von ihnen hergestellten Urkunden zu registrieren und aufzubewahren. Ihre entsprechenden Pflichten werden durch § 56 nNotG folgendermassen geregelt:
"1Die Notarin oder der Notar registriert alle Beurkundungen chronologisch und bewahrt von jeder Urkunde samt ihren Beilagen eine vollständige Kopie, auf Begehren der Klientschaft das Original, in der Urkundensammlung dauerhaft auf. § 54 Abs. 2 bleibt vorbehalten.
2Die Register und Urkundensammlungen stehen im Eigentum des Kantons. Sie sind bei Erlöschen der Beurkundungsbefugnis an das Notariatsarchiv abzuliefern, sofern nicht gemäss § 11 Abs. 4 vorgegangen wird.
3Der Regierungsrat ordnet das Nähere auf dem Verordnungswege."
Nachdem die Beschwerdeführer ihren Antrag entsprechend dem Eventualbegehren des Justizdepartements des Kantons Basel-Stadt präzisiert haben, wird vorliegend die Streichung des zweiten Teils des ersten Satzes von § 56 Abs. 2 nNotG ("...stehen im Eigentum des Kantons") verlangt. Zur Begründung dieses Antrags bringen die Beschwerdeführer vor, gemäss der abschliessenden Regelung des Bundeszivilrechts stünden die Urkunden im Eigentum des Notars, welcher die für ihre Herstellung notwendigen Materialien kaufe und anschliessend den Text verfasse; für eine "anderslautende kantonale Regelung", welche das Eigentum an Registern und Urkundensammlungen dem Kanton zuspreche, verbleibe kein Raum. Der Notar sei zudem als "Hüter der ihm anvertrauten Informationen" auf den Schutz angewiesen, welcher ihm die Stellung als Eigentümer der Urkundensammlung verleihe. Sinngemäss machen die Beschwerdeführer damit eine Verletzung des Vorrangs des Bundesrechts (<ref-law>) geltend.
6.2 Die streitbetroffenen Register und Urkundensammlungen werden zu ausschliesslich öffentlichen Zwecken erstellt und sind deshalb als öffentliche Sachen zu qualifizieren. Bei diesen Gegebenheiten ist der Kanton, welcher ohnehin zur Regelung der öffentlichen Beurkundung berufen ist (vgl. E. 2), auch kompetent, die Ausgestaltung der Rechtsverhältnisse an den Registern und Urkundensammlungen zu bestimmen. Namentlich kann er festlegen, inwieweit auf Letztere überhaupt Zivilrecht zur Anwendung kommen soll und - wenn dieses Geltung erlangt - wem das Eigentum an der öffentlichen Sache zustehen soll. Deshalb ist unbehelflich, wenn sich die Beschwerdeführer im vorliegenden Zusammenhang auf die Eigentumsregelung des Zivilgesetzbuchs berufen. Im Übrigen anerkennen die Beschwerdeführer neben der Aufbewahrungspflicht gemäss § 56 Abs. 1 nNotG ausdrücklich auch die in § 56 Abs. 2 Satz 2 nNotG statuierte Verpflichtung der Notare, bei Erlöschen der Beurkundungsbefugnis Register und Urkundensammlung dem Staat abzuliefern. Sie wenden sich einzig gegen die Regelung, wonach nicht der Notar selber, sondern der Kanton Eigentümer der von Ersterem verwahrten Urkunden ist. Dabei scheinen sie zu verkennen, dass die tatsächlichen Befugnisse des Notars in der vorliegenden Konstellation gar nicht von den Eigentumsverhältnissen abhängen. Selbst wenn der Notar - wie die Beschwerdeführer annehmen - zivilrechtlicher Eigentümer der Urkundensammlung wäre, würde er über keine der üblichen (materiellen) Befugnisse eines Eigentümers verfügen, zumal er die Urkunden sicher verwahren muss und weder verändern noch veräussern, verbrauchen oder vernichten darf. Seine tatsächliche Rechtsstellung unterscheidet sich insoweit nicht von jener eines blossen Besitzers. Ferner kommen dem Notar als Besitzer gegenüber Dritten grundsätzlich die gleichen Abwehrrechte zu wie einem Eigentümer (vgl. <ref-law>).
7. Mithin erweist sich die staatsrechtliche Beschwerde als unbegründet, soweit auf sie einzutreten ist.
Entsprechend dem Ausgang des Verfahrens werden die Beschwerdeführer - unter Solidarhaft - kostenpflichtig (Art. 156 Abs. 1 und Abs. 7 in Verbindung mit Art. 153 und Art. 153a OG). Parteientschädigung ist keine auszurichten (vgl. Art. 159 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 3'500.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
3. Dieses Urteil wird den Beschwerdeführern und dem Justizdepartement des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 21. August 2007
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: