Sachverhalt:
A. Der am 1. September 1977 geborene algerische Staatsangehörige X._ reiste Anfang 1998 unter Missachtung der Einreisevorschriften und unter falscher Identität in die Schweiz ein. Das von ihm eingereichte Asylgesuch wurde am 5. Februar 1998 rechtskräftig abgewiesen. Ein Gesuch um vorläufige Aufnahme wies das Bundesamt für Migration am 28. September 2004 ab. Sämtlichen Aufforderungen zur Ausreise kam X._ nicht nach. Auch ein Rückführungsversuch nach Algerien scheiterte an seinem Widerstand. X._ wurde in der Schweiz wiederholt straffällig. In der Zeit vom 2. März 1998 bis zum 14. Dezember 2007 ergingen gegen ihn total 16 Verurteilungen zu Freiheitsstrafen von insgesamt rund 33 Monaten. Den Verurteilungen lagen zum grössten Teil Vermögensdelikte sowie Widerhandlungen gegen aufenthaltsrechtliche Bestimmungen zu Grunde. Die längste einzelne Freiheitsstrafe betrug sechs Monate; sie wurde aufgrund einer Verurteilung wegen mehrfacher Widerhandlung gegen das Ausländergesetz, begangen durch Missachtung einer Ausgrenzungsverfügung, sowie wegen Hinderung einer Amtshandlung ausgesprochen.
B. Am 2. Juni 2008 heiratete X._ die Schweizerin Y._ und ersuchte danach um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Mit Verfügung vom 31. Oktober 2008 wies das Migrationsamt des Kantons Zürich das Gesuch insbesondere unter Hinweis auf die Delinquenz von X._ ab.
Hiergegen rekurrierten X._ und Y._ ohne Erfolg beim Regierungsrat des Kantons Zürich. Eine daraufhin beim Verwaltungsgericht des Kantons Zürich eingereichte Beschwerde wurde von diesem mit Urteil vom 17. März 2010 abgewiesen.
C. Mit Eingabe vom 11. Mai 2010 führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen im Wesentlichen die Aufhebung des vorinstanzlichen Entscheids und die Erteilung einer Aufenthaltsbewilligung für X._.
Das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
Mit Verfügung vom 18. Mai 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Ein Gesuch von X._ und Y._ um Sistierung des bundesgerichtlichen Verfahrens wurde dagegen mit Präsidialverfügung vom 27. September 2010 abgelehnt.
Die II. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 15. April 2011 an einer öffentlichen Sitzung beraten.

Erwägungen:
1. Art. 83 lit. c Ziff. 2 BGG erklärt die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide auf dem Gebiet des Ausländerrechts für unzulässig, soweit diese Bewilligungen betreffen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
Gemäss Art. 42 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Der Beschwerdeführer 1 ist seit dem 2. Juni 2008 mit einer Schweizer Bürgerin - der Beschwerdeführerin 2 - verheiratet und wohnt mit ihr zusammen. Er hat damit einen grundsätzlichen Anspruch auf Erteilung der Aufenthaltsbewilligung. Ein analoger Anspruch besteht zudem aufgrund von Art. 8 EMRK und Art. 13 Abs. 1 BV, da die ehelichen Beziehungen zwischen den Gatten soweit ersichtlich intakt sind und tatsächlich gelebt werden (vgl. <ref-ruling> E. 3.1 S. 285 f.; <ref-ruling> E. 5.3.1 S. 211 mit Hinweisen). Ob der Anspruch erloschen ist, weil - wie die Vorinstanzen angenommen haben - ein Widerrufsgrund nach Art. 63 AuG (in Verbindung mit Art. 51 Abs. 1 lit. b AuG) vorliegt, ist eine Frage der materiellen Beurteilung und nicht der Zulässigkeit des Rechtsmittels (<ref-ruling> E. 1.1.5 S. 149 f.).
Gemäss dem Gesagten steht im vorliegenden Fall die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen und es kann auf das im Übrigen form- und fristgerecht eingereichte Rechtsmittel eingetreten werden.
2. 2.1 Die Ansprüche nach Art. 42 des Ausländergesetzes erlöschen u.a. dann, wenn Widerrufsgründe nach Art. 63 AuG vorliegen (Art. 51 Abs. 1 lit. b AuG; vgl. E. 1 hiervor). Dies ist etwa dann der Fall, wenn eine ausländische Person zu einer längerfristigen Freiheitsstrafe verurteilt wurde (Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG). Das Bundesgericht hat definiert, dass eine Freiheitsstrafe als "längerfristig" gilt, wenn ihre Dauer ein Jahr überschreitet (<ref-ruling> E. 4.2 und E. 4.5 S. 379 ff.). Noch nicht ausdrücklich entschieden hat es die Frage, ob sich die mindestens einjährige Dauer der Freiheitsstrafe zwingend auf ein einziges Strafurteil stützen muss, oder ob auch mehrere kürzere Strafen, die zusammen mehr als ein Jahr ergeben, den Widerrufsgrund von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG erfüllen. In seiner bisherigen Rechtsprechung zu den genannten Bestimmungen prüfte das Bundesgericht aber jeweils, ob einzelne Straferkenntnisse für sich alleine das Kriterium der Längerfristigkeit erreichen (vgl. Urteil 2C_712/2009 vom 12. April 2010 Bst. A und E. 3).
2.2 Das Verwaltungsgericht führt in diesem Zusammenhang aus, es sei nicht einzusehen, weshalb zwar die Bewilligung jenes Ausländers zu widerrufen sei, der zu einer Freiheitsstrafe von 13 Monaten verurteilt wurde, nicht aber jene eines ausländischen Delinquenten, welcher vier Mal mit einer Freiheitsstrafe von jeweils 11 Monaten bestraft wurde. Im zweiten Fall sei der Unrechtsgehalt deutlich höher als beim ersten. Es seien nicht nur die ausgesprochenen Strafen insgesamt länger; ein mehrfach rückfälliger Täter gebe auch zu verstehen, dass er sich von Freiheitsstrafen nicht beeindrucken lasse und nicht bereit sei, sich an die gesetzliche Ordnung zu halten. Aus diesem Grund müssten auch mehrere kurze Freiheitsstrafen den Widerrufsgrund von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG erfüllen, sofern sie in ihrer Summe als "längerfristig" zu qualifizieren seien. Hierbei seien die ausgesprochenen Freiheitsstrafen aber nicht starr zu addieren, sondern vielmehr in einem Gesamtzusammenhang zu betrachten. Dies bedeute, dass etwa lange Zeitabstände zwischen den einzelnen Verurteilungen dazu führen könnten, dass nicht alle Straftaten berücksichtigt werden dürften.
2.2 Das Verwaltungsgericht führt in diesem Zusammenhang aus, es sei nicht einzusehen, weshalb zwar die Bewilligung jenes Ausländers zu widerrufen sei, der zu einer Freiheitsstrafe von 13 Monaten verurteilt wurde, nicht aber jene eines ausländischen Delinquenten, welcher vier Mal mit einer Freiheitsstrafe von jeweils 11 Monaten bestraft wurde. Im zweiten Fall sei der Unrechtsgehalt deutlich höher als beim ersten. Es seien nicht nur die ausgesprochenen Strafen insgesamt länger; ein mehrfach rückfälliger Täter gebe auch zu verstehen, dass er sich von Freiheitsstrafen nicht beeindrucken lasse und nicht bereit sei, sich an die gesetzliche Ordnung zu halten. Aus diesem Grund müssten auch mehrere kurze Freiheitsstrafen den Widerrufsgrund von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG erfüllen, sofern sie in ihrer Summe als "längerfristig" zu qualifizieren seien. Hierbei seien die ausgesprochenen Freiheitsstrafen aber nicht starr zu addieren, sondern vielmehr in einem Gesamtzusammenhang zu betrachten. Dies bedeute, dass etwa lange Zeitabstände zwischen den einzelnen Verurteilungen dazu führen könnten, dass nicht alle Straftaten berücksichtigt werden dürften.
2.3 2.3.1 Ausgangspunkt jeder Auslegung bildet der Wortlaut der Bestimmung. Ist der Text nicht klar und sind verschiedene Auslegungen möglich, so muss unter Berücksichtigung aller Auslegungselemente nach der wahren Tragweite gesucht werden. Abzustellen ist dabei namentlich auf die Entstehungsgeschichte der Norm und ihren Zweck sowie auf die Bedeutung, die der Norm im Kontext mit anderen Bestimmungen zukommt (<ref-ruling> E. 2.2 S. 418 mit Hinweisen).
2.3.2 Der Wortlaut von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG deutet darauf hin, dass sich die mindestens einjährige Strafdauer aus einem einzigen Urteil ergeben muss, spricht das Gesetz doch von "einer längerfristigen Freiheitsstrafe" ("une peine privative de liberté de longue durée"; "una pena detentiva di lunga durata").
2.3.3 Den Materialien zum Ausländergesetz kann sodann entnommen werden, dass die eidgenössischen Räte einen Antrag der vorberatenden Kommission des Nationalrates ausdrücklich ablehnten, welche statt dem Begriff der "längerfristigen Freiheitsstrafe" die Formulierung "wenn die Ausländerin oder der Ausländer zu einer Freiheitsstrafe von zwölf Monaten oder wiederholt zu einer kurzen Freiheits- oder Geldstrafe verurteilt wurde" in den Gesetzestext aufnehmen wollte (AB 2004 N 1083 ff.).
2.3.4 Entscheidend ist im vorliegenden Fall jedoch vor allem, dass sich das Bundesgericht bei seiner Definition des Begriffs "längerfristig" i.S. von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG massgeblich am Sanktionensystem des Strafgesetzbuches orientierte: Es führte aus, dass eine Freiheitsstrafe kaum als "längerfristig" bezeichnet werden könne, wenn sie sich in einem Rahmen bewege, der auch die Verurteilung zu einer Geldstrafe zulassen würde. Anders sei dagegen dort zu entscheiden, wo aufgrund des hohen Strafbedürfnisses zwingend eine Freiheitsstrafe als Sanktion ausgesprochen werden muss (<ref-ruling> E. 4.2 S. 380). Wie im genannten Urteil aufgezeigt wird, ist dies der Fall, wenn die Dauer der auszusprechenden Strafe ein Jahr bzw. 360 Tage überschreitet (Art. 34 Abs. 1 StGB). Unterhalb dieses Schwellenwertes, für Strafen von sechs Monaten bis zu einem Jahr, hat der Richter dagegen die Wahl, ob er eine Freiheitsstrafe oder aber eine Geldstrafe verhängt. Bis zu einer Strafdauer von sechs Monaten bzw. 180 Tagen steht als zusätzliche Sanktionsart auch die gemeinnützige Arbeit zur Verfügung, dafür sind kurze Freiheitsstrafen bis zu einer Dauer von sechs Monaten nur unter sehr einschränkenden Voraussetzungen möglich (vgl. Art. 37 Abs. 1 sowie Art. 41 Abs. 1 und Art. 42 Abs. 1 StGB).
Massgebliche Kriterien für die Wahl der Sanktionsart bilden ihre Zweckmässigkeit, ihre Auswirkungen auf den Täter und sein soziales Umfeld sowie ihre präventive Effizienz (<ref-ruling> E. 4.2 S. 100; <ref-ruling> E. 4.1 S. 84). Nicht massgeblich ist dagegen namentlich das Verschulden des Delinquenten; dieses schlägt sich ausschliesslich im Strafmass nieder. Die drei Hauptstrafarten (Freiheitsstrafe, Geldstrafe, gemeinnützige Arbeit) sind somit, was das Verschulden anbelangt, austauschbar (ANDREAS ZÜND, Strafrecht: Ein Wegweiser zu den neuen Sanktionen, Plädoyer 6/2008 S. 40).
Konsequenterweise müssten daher - wollte man der Argumentation des Verwaltungsgerichts folgen - auch allfällige Geldstrafen und Verurteilungen zu gemeinnütziger Arbeit bzw. die auf sie entfallende Anzahl Tagessätze resp. Arbeitsstunden zusammengerechnet und im Rahmen von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG berücksichtigt werden. Dies schliesst der klare Gesetzeswortlaut, welcher eindeutig von einer "Freiheitsstrafe" spricht, jedoch aus. Vor diesem Hintergrund erschiene es sachwidrig und unter dem Gesichtspunkt des Rechtsgleichheitsgebotes problematisch, die hinsichtlich des Verschuldens äquivalenten Freiheitsstrafen von einem Jahr oder weniger zu kumulieren.
2.3.5 Zu beachten ist sodann, dass das Bundesgericht seine Präzisierung des Begriffes "längerfristig" namentlich auch mit dem Interesse an Rechtssicherheit und einer einheitlichen Auslegung des Bundesrechts begründete (<ref-ruling> E. 4.2 S. 380). Diesem Bestreben würde durch die vom Verwaltungsgericht befürwortete grundsätzliche Möglichkeit einer Zusammenrechnung kürzerer Freiheitsstrafen entgegengewirkt: Wie die Vorinstanz richtig erkannt hat, müsste diesfalls unter Berücksichtigung der Umstände jedes Einzelfalls geklärt werden, bei welchen Straferkenntnissen eine Kumulation in Frage kommt. Namentlich wäre zu prüfen, ob es hierfür eines inhaltlichen Zusammenhangs oder einer zeitlichen Nähe verschiedener Urteile bedarf; gänzlich ausgeschlossen wäre ein Zusammenrechnen jedenfalls insoweit, als eine Verurteilung aus dem Strafregister entfernt wurde (vgl. Art. 369 Abs. 7 StGB; <ref-ruling> E. 2.10 S. 75 f. mit Hinweisen). Auch unter diesem Gesichtswinkel erscheint die von der Vorinstanz vertretene Auslegung von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG nicht als sinnvoll. Vielmehr ist bei der Rechtsanwendung ein Auslegungsergebnis anzustreben, welches praktikabel ist; im Zweifelsfall ist eine Lösung zu bevorzugen, welche den Anforderungen der Praxis gerecht wird (<ref-ruling> E. 3.3.4 S. 119 mit weiteren Hinweisen).
2.3.6 Aus dem Obenstehenden erhellt, dass bei der Prüfung des Widerrufsgrundes von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG auf ein Zusammenrechnen verschiedener Freiheitsstrafen von einem Jahr oder weniger zu verzichten ist. Der Widerrufsgrund ist vielmehr (nur) dann erfüllt, wenn eine Strafe für sich alleine das Kriterium der Längerfristigkeit erfüllt, d.h. die Dauer von einem Jahr überschreitet.
2.4 Wie bereits ausgeführt, haben die gegen den Beschwerdeführer 1 ausgesprochenen Freiheitsstrafen die Dauer eines Jahres jeweils nicht überschritten. Der Widerrufsgrund von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG ist somit nicht erfüllt und die Erteilung einer Aufenthaltsbewilligung darf dem Beschwerdeführer 1 deshalb nicht mit dieser Begründung verweigert werden (Art. 51 Abs. 1 lit. b AuG e contrario; vgl. E. 2.1 hiervor).
3. 3.1 Zu prüfen bleibt, ob der Beschwerdeführer 1 allenfalls in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen und mithin den Widerrufsgrund von Art. 63 Abs. 1 lit. b AuG erfüllt hat, wie dies die Vorinstanzen angenommen haben.
3.2 Gemäss Art. 80 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) liegt ein Verstoss gegen die öffentliche Sicherheit und Ordnung unter anderem vor bei einer Missachtung von gesetzlichen Vorschriften und behördlichen Verfügungen (Abs. 1 lit. a) sowie bei mutwilliger Nichterfüllung der öffentlich-rechtlichen oder privatrechtlichen Verpflichtungen (Abs. 1 lit. b). Anders als der Widerruf einer Aufenthaltsbewilligung (Art. 62 lit. c AuG), welcher voraussetzt, dass der Ausländer "erheblich oder wiederholt" gegen die öffentliche Sicherheit und Ordnung verstossen hat, bedingt ein Widerruf der Niederlassungsbewilligung i.S.v. Art. 63 Abs. 1 lit. b AuG - und damit ein Erlöschen des Anspruchs auf Familiennachzug gemäss Art. 51 Abs. 1 lit. b AuG -, dass ein solcher Verstoss "in schwerwiegender Weise" erfolgt ist. Dass damit vergleichsweise erhöhte Anforderungen an einen Bewilligungswiderruf gestellt werden, ergibt sich eindeutig aus dem französischen Wortlaut der genannten Bestimmungen: Während Art. 62 lit. c AuG von einem Verstoss "de manière grave ou répétée" spricht, wird in Art. 63 Abs. 1 lit. b AuG die qualifizierte Formulierung "de manière très grave" verwendet. Diese Unterscheidung überzeugt, vermittelt die Niederlassungsbewilligung doch das gefestigtere Anwesenheitsrecht als eine blosse Aufenthaltsbewilligung und besteht bei niedergelassenen Ausländern oftmals eine vergleichsweise engere Verbindung zur Schweiz (vgl. die Botschaft des Bundesrates vom 8. März 2002 zum Bundesgesetz über die Ausländerinnen und Ausländer, welche auf den "längeren Voraufenthalt der niedergelassenen Ausländerinnen und Ausländer" verweist [BBl 2002 3709 S. 3810]). Indes führt der unterschiedliche Wortlaut der Widerrufsgründe von Art. 62 lit. c AuG einerseits und Art. 63 Abs. 1 lit. b AuG andererseits zu erheblichen Abgrenzungsproblemen: Es erhellt nicht ohne weiteres, wann ein Verstoss gegen die öffentliche Sicherheit und Ordnung nicht nur als "erheblich oder wiederholt" erscheint, sondern überdies auch noch in einer Weise erfolgt ist, die als "schwerwiegend" bezeichnet werden muss. Diese unbestimmten Rechtsbegriffe erscheinen vielmehr in besonderem Masse als auslegungsbedürftig und sind nachfolgend näher zu umschreiben.
3.3 Zur Abgrenzung zwischen Art. 62 lit. c und Art. 63 Abs. 1 lit. b AuG erscheint es sachgerecht, in erster Linie auf den Stellenwert des beeinträchtigen Rechtsguts abzustellen: Wenn die ausländische Person durch ihre Handlungen besonders hochwertige Rechtsgüter wie namentlich die körperliche, psychische und sexuelle Integrität eines Menschen verletzt oder gefährdet hat, werden die qualifizierten Voraussetzungen von Art. 63 Abs. 1 lit. b AuG zumeist erfüllt sein. Indes können auch vergleichsweise weniger gravierende Pflichtverletzungen als "schwerwiegend" i.S.v. Art. 63 Abs. 1 lit. b AuG bezeichnet werden: In seiner Botschaft zum Ausländergesetz führt der Bundesrat aus, dass ein Widerruf der Niederlassungsbewilligung auch dann möglich sein soll, wenn sich eine ausländische Person von strafrechtlichen Massnahmen nicht beeindrucken lässt und damit zeigt, dass sie "auch zukünftig weder gewillt noch fähig ist, sich an die Rechtsordnung zu halten" (BBl 2002 3709 S. 3810).
Ob der Ausländer willens und in der Lage ist, sich in die hier geltende Ordnung einzufügen, kann nur anhand einer Gesamtbetrachtung seines Verhaltens beurteilt werden. Hieraus folgerte das Bundesgericht in früheren Entscheiden, dass auch eine Summierung von Verstössen, die für sich genommen für einen Widerruf nicht ausreichen würden, einen Bewilligungsentzug rechtfertigen könne; sogar das Bestehen von privatrechtlichen Schulden könne gegebenenfalls einen schwerwiegenden Verstoss gegen die öffentliche Sicherheit und Ordnung darstellen, wenn die Verschuldung mutwillig erfolgt ist (Urteil 2C_273/2010 vom 6. Oktober 2010 E. 3.2 und E. 3.3 mit Hinweisen). Dies muss umso mehr bei einer wiederholten Begehung von gewichtigen Vermögensdelikten gelten.
3.4 Im vorliegenden Fall hat der Beschwerdeführer 1 regelmässig, während einer langen Zeitspanne und ohne echte Not strafbare Handlungen begangen. Dabei handelte es sich, wie bereits ausgeführt, zumeist um Vermögensdelikte sowie um Verstösse gegen das Ausländerrecht. Dieses Verhalten des Beschwerdeführers 1 offenbart zweifelsohne eine bedenkliche Gleichgültigkeit gegenüber der schweizerischen Rechtsordnung.
Demgegenüber ist aber auch festzustellen, dass die verübten Vermögensdelikte schon eine gewisse Zeit zurückliegen; die letzte einschlägige Verurteilung datiert vom 23. Dezember 2004. Ebenso fällt auf, dass die vom Beschwerdeführer 1 begangenen Vermögensdelikte vergleichsweise tiefe Strafen von maximal drei Monaten nach sich gezogen haben. Die neueren Verurteilungen und die höheren Strafen betreffen vorwiegend - wenn auch nicht ausschliesslich - Widerhandlungen gegen das Ausländerrecht. Betreffend die Letzteren gilt es zudem zu berücksichtigen, dass die Erteilung der hier streitigen Bewilligung eo ipso zum Wegfall der Rechtswidrigkeit des Aufenthalts des Beschwerdeführers 1 führt und einer diesbezüglichen Delinquenz die Grundlage entzieht.
Aus diesen Gründen und in Anbetracht der aufgezeigten Abgrenzung zu Art. 62 lit. c AuG können die vom Beschwerdeführer 1 zu verantwortenden Verstösse gegen die öffentliche Sicherheit und Ordnung insgesamt nicht als "schwerwiegend" i.S.v. Art. 63 Abs. 1 lit. b AuG bezeichnet werden. Auch dieser Widerrufsgrund ist somit nicht erfüllt und darf daher nicht zur Begründung der Nichterteilung einer Aufenthaltsbewilligung herangezogen werden (Art. 51 Abs. 1 lit. b AuG e contrario; vgl. E. 2.1 und E. 2.4 hiervor.)
4. Ein Grund für den Widerruf bzw. die Verweigerung einer Niederlassungsbewilligung liegt auch dann vor, wenn der Ausländer oder eine Person, für die er zu sorgen hat, dauerhaft und in erheblichem Mass auf Sozialhilfe angewiesen ist (Art. 63 Abs. 1 lit. c i.V.m. Art. 51 Abs. 1 lit. b AuG). Das Migrationsamt und der Regierungsrat des Kantons Zürich erachteten diesen Widerrufsgrund im vorliegenden Fall als erfüllt. Das Verwaltungsgericht liess die Frage dagegen offen, zumal es davon ausging, dass der Beschwerdeführer 1 einerseits zu einer längerfristigen Freiheitsstrafe verurteilt worden sei und andererseits auch in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung verstossen habe. Da die Voraussetzungen von Art. 63 Abs. 1 lit. a (i.V.m. Art. 62 lit. b) und Art. 63 Abs. 1 lit. b AuG nach dem Ausgeführten jedoch nicht gegeben sind, erweist es sich als notwendig, dass sich die Vorinstanz zu diesem Punkt ausspricht.
5. Aus den obenstehenden Erwägungen folgt, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten gutzuheissen ist. Das angefochtene Urteil des Verwaltungsgerichts des Kantons Zürich vom 17. März 2010 ist aufzuheben und die Angelegenheit ist zur Neubeurteilung (insbesondere zur Prüfung des Widerrufsgrundes von Art. 63 Abs. 1 lit. c AuG) an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 66 Abs. 1 und Abs. 4 BGG) und es ist den Beschwerdeführern eine angemessene Parteientschädigung zuzusprechen (Art. 68 Abs. 2 BGG). Damit wird das von ihnen gestellte Gesuch um unentgeltliche Prozessführung und Verbeiständung gegenstandslos. Die Parteientschädigung ist jedoch der Rechtsvertreterin der Beschwerdeführer zu entrichten.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 17. März 2010 aufgehoben und die Sache zu neuem Entscheid im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Zürich hat der Rechtsvertreterin der Beschwerdeführer eine Parteientschädigung von Fr. 2'000.-- für das bundesgerichtliche Verfahren auszurichten.
4. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion und dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. April 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Zähndler