Sachverhalt:
A. X.a._ (geb. 1945) ist selbständiger Kaufmann mit der Einzelfirma "X._ Consulting" mit Geschäftssitz in Zug. Für die Steuerperioden 2004 - 2007 ordnete das Steueramt Zürich eine Bücherrevision an und erliess am 17. August 2009 eine erste Auflage zur Einreichung diverser Unterlagen; einverlangt wurden u.a. eine "detaillierte Aufstellung über sämtliche Einnahmen und Ausgaben 2004 - 2007 aus selbständiger Erwerbstätigkeit", ebenso der "Nachweis des effektiven Geschäftssitzes in Zug für 2004 - 2007 anhand der Telefonrechnungen, Stromrechnungen, Geschäftskorrespondenzen, Mietverträge etc.". Am 22. Februar 2010 erliess das Steueramt eine zweite, detailliertere Auflage und verlangte weitere Unterlagen. Nach reger Korrespondenz, in deren Verlauf X.a._ vom Steueramt zwei Mal gemahnt wurde, erliess das Amt am 21. November 2010 hinsichtlich der Staats- und Gemeindesteuern für die Steuerjahre 2004, 2005, 2006 und 2007 die Einschätzungsverfügungen. Dabei veranlagte es die selbständigen Erwerbseinkünfte "mangels vollständigem Erfüllen der Auflage des Bücherrevisors vom 22. Februar 2010" gestützt auf § 139 Abs. 2 des kantonalen Steuergesetzes (StG) nach pflichtgemässem Ermessen. Identisch, aber auf bundesrechtlicher Grundlage, verfuhr das Steueramt hinsichtlich der Direkten Bundessteuer.
Gegen sämtliche Ermessenstaxationen erhoben die Eheleute X._ mit Eingaben vom 28. Dezember 2010 und 12. Januar 2011 Einsprache.
B. Mit teilweise gutheissenden Einspracheentscheiden vom 6. Juni 2011 schätzte das kantonale Steueramt Zürich die Eheleute X._ hinsichtlich der Staats- und Gemeindesteuern 2004 - 2007 mit einem steuerbaren Einkommen von Fr. 167'200.--, Fr. 152'000.--, Fr. 150'300.-- bzw. Fr. 145'700.-- und einem steuerbaren Vermögen von Fr. 638'000.--, Fr. 653'000.--, Fr. 535'000.-- bzw. Fr. 333'000.-- ein. Die Einsprachen hinsichtlich der Direkten Bundessteuer wies es gleichentags ab.
Hiegegen erhoben die Eheleute X._ am 18. Juli 2011 (persönlich überbracht) die ihnen zustehenden Rechtsmittel beim kantonalen Steuerrekursgericht, auf welche dieses - nachdem es den Steuerpflichtigen die Gelegenheit eingeräumt hatte, sich zur Fristwahrung zu äussern - mit Beschluss vom 28. Oktober 2011 nicht eintrat, weil die Rechtsmittel - ohne entschuldbaren Grund - verspätet erhoben worden seien.
Mit zwei Urteilen vom 11. April 2012 (SB.2011.00168 hinsichtlich der Staats- und Gemeindesteuern bzw. SB.2011.00169 hinsichtlich der Direkten Bundessteuer) wies das Verwaltungsgericht des Kantons Zürich die gegen den Beschluss des Steuerrekursgerichtes vom 28. Oktober 2011 erhobene Beschwerde ab.
C. Mit gemeinsamer Eingabe vom 8. Juni 2012 führen die Eheleute X._ gegen "ein Urteil des Verwaltungsgerichts des Kantons Zürich vom 11. April 2012" Beschwerde beim Bundesgericht. Sie legen ihrer Eingabe das Urteil SB.2011.001168 bei und beantragen, dieses sei aufzuheben und das Verfahren zur Neuentscheidung im Sinne der Beschwerde an die Vorinstanz zurückzuweisen.
Das Steueramt beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Verwaltungsgericht stellt denselben Antrag; die Eidgenössische Steuerverwaltung verzichtet auf Antragstellung.
Mit Verfügung vom 13. Juni 2012 hat der Abteilungspräsident das gleichzeitig mit der Beschwerdeerhebung gestellte Gesuch um aufschiebende Wirkung abgewiesen.
Mit Eingabe vom 2. Oktober 2012 haben sich die Eheleute X._ noch einmal geäussert.
D. Am 18. Juli 2012 trat das Bundesgericht auf die am 13. Juli 2012 erhobene Beschwerde gegen das Urteil SB.011.00169 hinsichtlich der Direkten Bundessteuer (vorne lit. B) nicht ein; das entsprechende Fristwiederherstellungsgesuch wies es ab (Verfahren 2C_700/2012).

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig (vgl. <ref-law> in Verbindung mit Art. 73 des Bundesgesetzes vom 14. Dezember 1990 über die Harmonisierung der direkten Steuern der Kantone und Gemeinden [StHG; SR 642.14]).
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (Motivsubstitution; <ref-ruling> E. 2.2 S. 540; <ref-ruling> E. 3 S. 386; <ref-ruling> E. 2.2 S. 550). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, soweit er nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 Abs. 1 und 2 BGG).
1.3 Fragen des Bundesrechts klärt das Bundesgericht mit freier Kognition (<ref-law>, Urteile 2C_708/2012 vom 21. Dezember 2012 E. 1.4; 2C_92/2012 vom 17. August 2012 E. 1.4, in: StR 67/2012 S. 828). Besteht kein Gestaltungsspielraum zugunsten des kantonalen Gesetzgebers, der die sog. Willkürkognition nach sich zöge, prüft das Bundesgericht die Anwendung des harmonisierten kantonalen Rechts mit freier Kognition, ebenso, wie es dies im Fall von Bundesrecht täte (<ref-ruling> E. 2 S. 210). Kantonales Verfahrensrecht kann das Bundesgericht nur auf Verletzung verfassungsmässiger Rechte, namentlich auf Willkür hin überprüfen (<ref-law>; vgl. 134 II 349 E. 3 S. 351; 134 II 379 E. 1.2 S. 382/383), wenn und soweit entsprechende Rügen erhoben und begründet werden, d.h. klar und detailliert anhand der Erwägungen des angefochtenen Urteils dargelegt wird, inwiefern verfassungsmässige Rechte verletzt sein sollen (<ref-law>; <ref-ruling> E. 3.2 S. 88).
2. Das Verwaltungsgericht stellte fest, die betroffenen Einspracheentscheide seien den Steuerpflichtigen am 7. Juni 2011 zur Abholung gemeldet worden. Infolge eines aus Deutschland erteilten Fristverlängerungs- bzw. Zurückbehaltungsauftrags (an die Post) habe der Ehemann die Entscheide aber erst am 18. Juni 2011 am Postschalter in Empfang genommen.
Alsdann griff das Verwaltungsgericht zur so genannten "Zustellungsfiktion" (auch: "Zustellfiktion"): Stellt die Behörde eine Vorladung, eine Verfügung oder einen Entscheid durch eingeschriebene Postsendung zu und wird die Postsendung nicht abgeholt, so gilt die Zustellung am siebten Tag nach dem erfolglosen Zustellungsversuch als erfolgt, sofern der Adressat mit einer Zustellung rechnen musste (<ref-ruling> E. 3.1, 134 V 49 E. 4, <ref-ruling> E. 1.2.3, vgl. auch <ref-law> [SR 272], in Kraft seit 1. Januar 2011). Die Geltung der Zustellungsfiktion setzt ein hängiges bzw. laufendes Verfahren voraus; d.h. das relevante Prozessrechtsverhältnis entsteht erst mit Rechtshängigkeit (<ref-ruling> E. 3.1; <ref-ruling> E. 1.2.3; 5D_130/2011 E. 2.1). Die Zustellfiktion gilt auch dann, wenn gegenüber der Post für eine gewisse Dauer ein Zurückbehaltungsauftrag erteilt wurde (vgl. Urteil 4A_660/2011 vom 9. Februar 2012 E. 2.4, mit Hinweis auf <ref-ruling> E. 4 S. 52, ferner Urteile 2C_740/2010 vom 3. März 2011 E. 2.3 bzw. 1C_85/2010 vom 4. Juni 2010 E. 1.4;), und entspricht verschiedenen gesetzlichen Regelungen (vgl. etwa <ref-law>, <ref-law>, <ref-law> und <ref-law>). Der Betroffene kann sich dagegen schützen, indem er beispielsweise die Behörde auf eine bevorstehende Abwesenheit aufmerksam macht, so dass diese auf eine Zustellung in dieser Zeit verzichtet (vgl. Urteil 4A_660/2011 vom 9. Februar 2012 E. 2.4.2).
Sodann erwog das Verwaltungsgericht, aufgrund der erhobenen Einsprachen gegen die Einschätzungsentscheide hätten sich die Steuerpflichtigen in einem Prozessrechtsverhältnis befunden und deshalb mit der Zustellung der Einspracheentscheide rechnen müssen. Diese gälten damit als am siebten Tag der Abholfrist, mithin am 14. Juni 2011, als zugestellt. Folglich habe die Rekursfrist von 30 Tagen (§ 147 Abs. 1 StG) am 15. Juni 2011 zu laufen begonnen und am 14. Juli 2011 geendet, womit der am 18. Juli 2011 deponierte Rekurs verspätet erhoben worden sei.
3. 3.1 Die Beschwerdeführer stellen das Bestehen eines Prozessrechtsverhältnisses nicht in Frage (S. 4 der Beschwerdeschrift). Sie rügen aber als willkürlich und als Verletzung des Grundsatzes von Treu und Glauben, wenn das Verwaltungsgericht annehme, sie hätten mit der Zustellung der Einspracheentscheide "gerade im Juni 2011" rechnen müssen. So habe etwa keine Einspracheverhandlung stattgefunden. Sie hätten aber davon ausgehen können, zunächst werde eine Einigungsverhandlung angesetzt. Sodann hätten sich die Veranlagungsverfahren über Jahre hingezogen: Entschieden worden sei im Juni 2011 beispielsweise über Einsprachen betreffend die Steuerperiode 2004; für die Beschwerdeführer sei aber unvorhersehbar gewesen "dass die Einspracheentscheide für sämtliche hängigen Steuerperioden gerade am 7. Juni 2011 verschickt würden".
3.2 Diese Einwände dringen nicht durch: Zunächst wird gemäss unwiderlegter zürcherischer Praxis eine Einspracheverhandlung nur auf Antrag des Steuerpflichtigen durchgeführt (vgl. § 141 Abs. 2 StG) und die Beschwerdeführer haben, wie das Steueramt vernehmlassungsweise unwidersprochen ausführt, keinen solchen Antrag gestellt. Sodann trifft zwar zu, dass bei der Anwendung der Regeln über die Zustellungsfiktion auch der Verfahrensdauer Rechnung zu tragen ist; vom Betroffenen kann nicht erwartet werden, dass er bei einem hängigen Verfahren über Jahre hinweg in jedem Zeitpunkt erreichbar sein und auch kürzere Ortsabwesenheiten der Behörde melden muss, um keinen Rechtsnachteil zu erleiden (vgl. Urteil 2P.120/2005 vom 23. März 2006 E. 4.2). Das Bundesgericht hat verschiedentlich einen Zeitraum von bis zu einem Jahr seit der letzten verfahrensrechtlichen Handlung der Behörde als vertretbar erachtet (vgl. Urteil 6B_511/2010 vom 13. August 2010 E. 3 mit Hinweisen). Der hier vergangene Zeitraum gibt keinen Anlass zur Beanstandung, wurden doch die Veranlagungsverfahren für die Steuerperioden 2004 - 2007 in den Jahren 2009 und 2010 alle gemeinsam durchgeführt und ergingen die entsprechenden Veranlagungsverfügungen alle am 21. November 2010 (vorne lit. A), also rund sieben Monate vor der Zustellung der Einspracheentscheide am 7. Juni 2011). Bei dieser Sachlage kann nicht von einer willkürlichen oder treuwidrigen Anwendung der Zustellungsfiktion gesprochen werden.
3.2 Diese Einwände dringen nicht durch: Zunächst wird gemäss unwiderlegter zürcherischer Praxis eine Einspracheverhandlung nur auf Antrag des Steuerpflichtigen durchgeführt (vgl. § 141 Abs. 2 StG) und die Beschwerdeführer haben, wie das Steueramt vernehmlassungsweise unwidersprochen ausführt, keinen solchen Antrag gestellt. Sodann trifft zwar zu, dass bei der Anwendung der Regeln über die Zustellungsfiktion auch der Verfahrensdauer Rechnung zu tragen ist; vom Betroffenen kann nicht erwartet werden, dass er bei einem hängigen Verfahren über Jahre hinweg in jedem Zeitpunkt erreichbar sein und auch kürzere Ortsabwesenheiten der Behörde melden muss, um keinen Rechtsnachteil zu erleiden (vgl. Urteil 2P.120/2005 vom 23. März 2006 E. 4.2). Das Bundesgericht hat verschiedentlich einen Zeitraum von bis zu einem Jahr seit der letzten verfahrensrechtlichen Handlung der Behörde als vertretbar erachtet (vgl. Urteil 6B_511/2010 vom 13. August 2010 E. 3 mit Hinweisen). Der hier vergangene Zeitraum gibt keinen Anlass zur Beanstandung, wurden doch die Veranlagungsverfahren für die Steuerperioden 2004 - 2007 in den Jahren 2009 und 2010 alle gemeinsam durchgeführt und ergingen die entsprechenden Veranlagungsverfügungen alle am 21. November 2010 (vorne lit. A), also rund sieben Monate vor der Zustellung der Einspracheentscheide am 7. Juni 2011). Bei dieser Sachlage kann nicht von einer willkürlichen oder treuwidrigen Anwendung der Zustellungsfiktion gesprochen werden.
3.3 3.3.1 Die Beschwerdeführer machen geltend, sie hätten dem Verwaltungsgericht "ernsthafte Gründe für ihre Auslandsabwesenheit" genannt und diese auch belegt. Es sei deshalb willkürlich, wenn das Verwaltungsgericht annehme, sie hätten die Zustellung der Einspracheentscheide "schuldhaft" verhindert. Ebenso willkürlich sei es, die Fristen nicht wieder herzustellen.
3.3.2 § 15 Abs. 1 der kantonalen Verordnung vom 1. April 1998 zum Steuergesetz (VO StG) hat folgenden Wortlaut:
1 Hat ein Steuerpflichtiger eine Frist für die Geltendmachung eines Rechtes versäumt, ist Wiederherstellung zu gewähren, wenn er nachweist, dass er oder sein Vertreter ohne Verschulden entweder von der Fristansetzung nicht rechtzeitig Kenntnis erhalten hat oder durch schwerwiegende Gründe an der Einhaltung der Frist verhindert worden ist. Als schwerwiegende Gründe gelten z.B. Krankheit, Todesfall in der Familie, Landesabwesenheit oder Militärdienst.
3.3.3 Nach der zürcherischen Praxis liegt generell eine schuldhafte Verhinderung vor, wenn der Adressat die erforderlichen Vorkehren für die Zustellbarkeit von behördlichen Postsendungen unterlässt, obwohl er aufgrund des Bestehens eines Prozessrechtsverhältnisses nach Treu und Glauben die Zustellung eines behördlichen Aktes im konkreten Einzelfall mit einer gewissen Wahrscheinlichkeit erwarten musste. Trifft dies zu, hat er deshalb bei längerer Ortsabwesenheit geeignete Massnahmen zu treffen, um dessen ordnungsgemässe Zustellung zu gewährleisten, beispielsweise durch einen Nachsendeauftrag, die Bekanntgabe der Abwesenheit oder der Adressänderung oder durch die Bestellung eines Zustellungsbevollmächtigten. Wer Vorkehren dieser Art unterlässt, verhindert schuldhaft die Zustellung, und eine Fristwiederherstellung ist ausgeschlossen (RICHNER/FREI/KAUFMANN/MEUTER, Kommentar zum harmonisierten Zürcher Steuergesetz, 2. Auflage 2006, Rz. 38 und 40 zu § 126 sowie Rz. 40 zu § 129).
3.3.4 Das Verwaltungsgericht hat erwogen, zwar könne gestützt auf § 15 Abs. 1 VO StG eine versäumte Frist infolge Landesabwesenheit wiederhergestellt werden. Eine solche Fristwiederherstellung setze aber immer voraus, dass die Fristversäumnis nicht auf ein Verschulden des Säumigen zurückzuführen sei. Mit seinem aus Deutschland erteilten Auftrag an die Post, die Abholfrist zu verlängern (recte: die Post bis zum 18. Juni 2011 aufzubewahren [vgl. Stellungnahme des Beschwerdeführers vom 24. August 2011 an das Steuergericht]), habe der Ehemann die ordnungsgemässe Zustellung der amtlichen Sendung jedoch schuldhaft verhindert, weshalb die Fristwiederherstellung bereits am Erfordernis der Schuldlosigkeit an der eingetretenen Säumnis scheitere.
3.3.5 Inwiefern und unter welchen Umständen die vom Verwaltungsgericht angewendete kantonale Praxis zur - wie das Gericht und die Doktrin sie nennt - "schuldhaften Verhinderung einer Zustellung" in einem konkreten Einzelfall in Willkür umschlagen könnte, kann hier offen bleiben: Als willkürlich gilt ein Entscheid nur dann, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 S. 5; <ref-ruling> E. 3.1 S. 178; je mit Hinweisen).
Vorliegend hat der Beschwerdeführer 1 die streitbetroffenen Einspracheentscheide am 18. Juni 2011 persönlich auf der Poststelle in Empfang genommen. Die Rekursfrist für die Rechtsmittel an das Steuerrekursgericht lief, da die Beschwerdeführer mit der Zustellung der Einspracheentscheide rechnen mussten (vorne E. 3.2), in korrekter Anwendung der Zustellungsfiktion am 14. Juli 2011 ab. Es hätten den Steuerpflichtigen damit mehr als dreieinhalb Kalenderwochen zur Verfügung gestanden, um die Einspracheentscheide fristgerecht beim Steuerrekursgericht anzufechten bzw. anfechten zu lassen. Da es ihnen unter diesen Umständen ohne weiteres möglich gewesen wäre, innert Frist zu handeln, erscheint es nicht willkürlich, wenn das Verwaltungsgericht eine Fristwiederherstellung als ausgeschlossen betrachtet hat.
Dass die Beschwerdeführer im kantonalen Verfahren nicht anwaltlich vertreten waren und juristische Laien sind, ändert an diesem Ergebnis nichts: Die erhebliche Formenstrenge und die ihnen obliegende Sorgfaltspflicht beim Empfang behördlicher Akte hätte ihnen schon aufgrund des bundesgerichtlichen Urteils 2C_301/2008 vom 16. Oktober 2008 (betreffend Wiederherstellung der Rekursfrist gegen die Veranlagung der Staats- und Gemeindesteuern für die Steuerperiode 2003) bewusst sein müssen.
4. Dies führt zur Abweisung der Beschwerde.
Bei diesem Ausgang sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen, unter solidarischer Haftung (Art. 65 sowie Art. 66 Abs. 1 und BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt, unter solidarischer Haftung.
3. Dieses Urteil wird den Beschwerdeführern, dem Kantonalen Steueramt Zürich, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und der Eidgenössischen Steuerverwaltung schriftlich mitgeteilt.
Lausanne, 11. April 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein