Sachverhalt:
A. Am 7. Mai 2006 fuhr X._ innerorts auf der Zürichstrasse in Aathal-Seegräben Richtung Uster mit einer rechtlich massgebenden Geschwindigkeit (d.h. unter Abzug einer Sicherheitsmarge von 5 km/h) von 80 km/h. Die zulässige Höchstgeschwindigkeit betrug 50 km/h. Mit Strafbefehl vom 29. August 2006 auferlegte ihm die Staatsanwaltschaft See/Oberland wegen grober Verletzung der Verkehrsregeln gemäss <ref-law> eine Busse von Fr. 1'200.--. Mit Verfügung vom 31. Januar 2007 entzog ihm sodann die Sicherheitsdirektion des Kantons Zürich gestützt auf Art. 16c Abs. 1 lit. a und Abs. 2 lit. a SVG den Führerausweis für drei Monate. Den gegen diese Verfügung gerichteten Rekurs wies der Regierungsrat des Kantons Zürich mit Entscheid vom 7. Mai 2008 ab. X._ gelangte in der Folge mit Beschwerde an das Verwaltungsgericht des Kantons Zürich. Das Verwaltungsgericht hiess das Rechtsmittel mit Entscheid vom 11. Februar 2009 teilweise gut und reduzierte die Entzugsdauer auf zwei Monate. Zur Begründung führte es eine Verletzung des Beschleunigungsgebots durch die Vorinstanzen an. Die Dauer des Verfahrens vor der Sicherheitsdirektion von etwa vier Monaten und jene des Verfahrens vor dem Regierungsrat von dreizehn Monaten seien zu lang gewesen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 26. März 2009 beantragt das Bundesamt für Strassen (ASTRA), der Entscheid des Verwaltungsgerichts sei aufzuheben und X._ sei der Führerausweis für die Dauer von drei Monaten zu entziehen. Das ASTRA macht geltend, der angefochtene Entscheid verletze Art. 16 Abs. 3 i.V.m. Art. 16c Abs. 1 lit. a und Abs. 2 lit. a SVG.
Die Sicherheitsdirektion beantragt in ihrer Vernehmlassung die Gutheissung der Beschwerde. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei, ebenso im Wesentlichen der Beschwerdegegner.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid über einen Führerausweisentzug. Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten zur Verfügung (<ref-law>; vgl. auch <ref-law>). Ein Ausnahmegrund ist nicht gegeben (<ref-law>).
Das ASTRA ist gestützt auf <ref-law> i.V.m. Art. 10 Abs. 4 der Organisationsverordnung vom 6. Dezember 1999 für das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation (OV-UVEK; SR 172.217.1) zur Beschwerde legitimiert. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2. 2.1 Das beschwerdeführende Amt ist der Ansicht, dass <ref-law> es verbiete, die Mindestentzugsdauer von drei Monaten zu unterschreiten. Der Beschwerdegegner erwidert, <ref-law> befasse sich lediglich mit persönlichen Umständen. Die Vorschrift sei im vorliegenden Fall, wo es um eine Verletzung des Beschleunigungsgebots gehe, nicht anwendbar und die Unterschreitung der Mindestentzugsdauer deshalb zulässig.
2.2 Nach der früheren Rechtsprechung zu den altrechtlichen Administrativmassnahmen konnte die Mindestentzugsdauer unterschritten und allenfalls von der Anordnung einer Massnahme abgesehen werden, wenn seit dem massnahmeauslösenden Ereignis verhältnismässig lange Zeit verstrichen war, sich der Betroffene während dieser Zeit wohl verhalten hatte und ihn an der Verfahrensdauer keine Schuld traf (<ref-ruling> E. 4e S. 510). In späteren Entscheiden wurde die Möglichkeit, die gesetzliche Mindestentzugsdauer zu unterschreiten, bestätigt (vgl. etwa <ref-ruling> E. 3d S. 300; <ref-ruling> E. 2a-b S. 108 f.; je mit Hinweisen).
Das Administrativmassnahmenrecht des Strassenverkehrsgesetzes wurde per 1. Januar 2005 verschärft. Gemäss <ref-law> darf die Mindestentzugsdauer nun nicht mehr unterschritten werden. Ziel der Revision war "eine einheitlichere und strengere Ahndung von schweren und wiederholten Widerhandlungen gegen Strassenverkehrsvorschriften" (Botschaft vom 31. März 1999 zur Änderung des Strassenverkehrsgesetzes [SVG], BBl 1999 S. 4485). Die besonderen Umstände des Einzelfalls, namentlich die Gefährdung der Verkehrssicherheit, das Verschulden, der Leumund als Motorfahrzeugführer sowie die berufliche Notwendigkeit, ein Motorfahrzeug zu führen, sollen neu nur bis zur gesetzlich vorgeschriebenen Mindestentzugsdauer berücksichtigt werden können (vgl. <ref-law>; Urteile des Bundesgerichts 1C_275/2007 vom 16. Mai 2008 E. 4.5; 6A.61/2006 vom 23. November 2006 E. 4.3 f., in: JdT 2007 I 502; 6A.38/2006 vom 7. September 2006 E. 3.1.2, in: JdT 2006 I 412; je mit Hinweisen). Zu den bei der Festsetzung des Führerausweisentzugs zu berücksichtigenden Umständen zählt wie unter dem früheren Recht auch die Verletzung des Anspruchs auf Beurteilung innert angemessener Frist (<ref-law>, Art. 6 Ziff. 1 EMRK; siehe auch BBl 1999 S. 4486, wo auf die entsprechende frühere "Bundesgerichtspraxis, eingeführt mit <ref-ruling>" hingewiesen wird). Entsprechend kommt die Unterschreitung der Mindestentzugsdauer wegen einer Verletzung dieses Anspruchs nicht mehr in Frage. Der angefochtene Entscheid verletzt <ref-law> und ist aufzuheben.
2.3 Eine andere Frage ist, ob - ebenfalls nach Massgabe des früheren Rechts - bei einer schweren Verletzung des Anspruchs auf Beurteilung innert angemessener Frist, der nicht in anderer Weise Rechnung getragen werden kann, ausnahmsweise gänzlich auf eine Massnahme verzichtet werden kann (siehe für das Strafrecht: <ref-ruling> E. 8 S. 170; Urteil 6B_801/2008 vom 12. März 2009 E. 3.5; je mit Hinweis). Die Frage braucht nicht weiter erörtert zu werden, da hier, wo bis zum Entscheid der Sicherheitsdirektion etwa vier und bis zu jenem des Regierungsrats dreizehn Monate vergingen, kein solcher Fall vorliegt. Es ist auch nicht ersichtlich, dass die zur Diskussion stehende Massnahme durch den Zeitablauf ihrer erzieherischen Wirkung beraubt worden wäre (vgl. <ref-ruling> E. 3d S. 300 mit Hinweisen).
3. Die Vorinstanz hätte von einer Reduktion der Dauer des Führerausweisentzugs absehen und es in teilweiser Gutheissung der Beschwerde bei einer Feststellung der Verletzung des Anspruchs auf Beurteilung innert angemessener Frist bewenden lassen müssen (vgl. etwa <ref-ruling> E. 5.3 S. 333 mit Hinweis; Urteil des EGMR P.B. gegen Frankreich vom 1. August 2000 § 52). Das angefochtene Urteil ist deshalb auch diesbezüglich aufzuheben und es ist festzustellen, dass der Anspruch des Beschwerdegegners auf Beurteilung innert angemessener Frist verletzt worden ist (<ref-law>).
Dementsprechend unterliegt der Beschwerdegegner im Verfahren vor Bundesgericht lediglich teilweise. Es erscheint angemessen, ihm die Hälfte der Gerichtskosten von Fr. 2'000.-- aufzuerlegen (<ref-law>). Aus dem gleichen Grund hat er Anspruch auf eine reduzierte Parteientschädigung (Art. 68 Abs. 1 und 2 BGG). Weder dem Bund noch dem Kanton Zürich werden Gerichtskosten auferlegt (<ref-law>).
Das Bundesgericht kann nach Massgabe von Art. 67 und Art. 68 Abs. 5 BGG die Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens ändern. Die Vorinstanz auferlegte dem Beschwerdegegner zwei Drittel der Kosten und verzichtete darauf, ihm eine Parteientschädigung zuzusprechen. Diese Kosten- und Entschädigungsfolgen erweisen sich trotz der Änderung des angefochtenen Entscheids in der Sache weiterhin als gerechtfertigt, zumal zwar die Dauer des Führerausweisentzugs erhöht, gleichzeitig aber eine Verletzung des Anspruchs auf Beurteilung innert angemessener Frist festgestellt wird.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird im Sinne der Erwägungen teilweise gutgeheissen und Ziff. 1 des Dispositivs des angefochtenen Entscheids aufgehoben.
2. Der Führerausweis wird für die Dauer von drei Monaten entzogen.
3. Es wird festgestellt, dass die Verwaltungsbehörden den Anspruch des Beschwerdegegners auf Beurteilung innert angemessener Frist verletzt haben.
4. Die Gerichtskosten werden dem Beschwerdegegner im Umfang von Fr. 1'000.-- auferlegt.
5. Der Kanton Zürich hat dem Beschwerdegegner eine reduzierte Parteientschädigung von Fr. 1'000.-- zu bezahlen.
6. Dieses Urteil wird den Parteien, der Sicherheitsdirektion und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 1. September 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold