Sachverhalt:
A. Der serbische Staatsangehörige X._, geb. 1955, hat aus erster Ehe mit einer Landsfrau zwei heute volljährige Kinder. Am 18. Februar 2004 heiratete er die in der Schweiz niedergelassene A._ (geb. 1980), worauf ihm die Aufenthaltsbewilligung für den Kanton Zürich erteilt wurde.
In der Folge stellte sich heraus, dass gegen X._ in Deutschland verschiedene Strafurteile ergangen sind. So wurde er unter anderem, nachdem er 2001 von der Schweiz an Deutschland ausgeliefert worden war, am 18. Februar 2002 vom Landgericht Bielefeld wegen Vergewaltigung und Betrug zu einer Freiheitsstrafe von drei Jahren und drei Monaten verurteilt. Nach Entlassung aus dem Strafvollzug im Mai 2003 wurde er aus der BRD ausgewiesen und in sein Heimatland abgeschoben.
Weil er im Gesuch um Erteilung der Aufenthaltsbewilligung wahrheitswidrig angegeben hatte, weder in der Schweiz noch im Ausland vorbestraft zu sein, wurde X._ am 4. November 2004 vom Stadtrichter von Zürich wegen Zuwiderhandlung gegen fremdenpolizeiliche Vorschriften mit einer Busse von Fr. 500.-- bestraft.
B. Mit Blick auf die genannten Umstände verweigerte die Direktion für Soziales und Sicherheit des Kantons Zürich, Migrationsamt, X._ mit Verfügung vom 5. November 2004 die Verlängerung der Aufenthaltsbewilligung. Dagegen rekurrierte der Betroffene erfolglos an den Regierungsrat des Kantons Zürich (Entscheid vom 14. Dezember 2005). Auf eine hiegegen erhobene Beschwerde trat das Verwaltungsgericht des Kantons Zürich am 12. Juli 2006 unter anderem aufgrund eines veränderten Sachverhalts nicht ein: Im Dezember 2005 hatte sich X._ in seiner Heimat von seiner zweiten Ehefrau scheiden lassen und am 26. April 2006 die Schweizer Bürgerin B._ (geb. 1968) geheiratet, um sich nunmehr im fremdenpolizeilichen Verfahren auf diese Ehe zu berufen.
C. Mit Verfügung vom 15. Januar 2007 wies das Migrationsamt das am 3. Mai 2006 von X._ eingereichte Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei seiner Schweizer Ehefrau ab. Gegen diese Verfügung legte X._ erfolglos Rekurs beim Regierungsrat ein (Beschluss vom 19. Dezember 2007). Mit Entscheid vom 16. April 2008 wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, eine hiegegen gerichtete Beschwerde ab.
D. Mit Eingabe vom 5. Juni 2008 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den Entscheid des Verwaltungsgerichts vom 16. April 2008 aufzuheben und dem Gesuch um Erteilung resp. Verlängerung der Aufenthaltsbewilligung stattzugeben.
Die Staatskanzlei (im Auftrag des Regierungsrates) des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich (4. Kammer) verzichtet auf eine Vernehmlassung.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
Der Beschwerdeführer ist mit einer Schweizerin verheiratet, womit er gestützt auf Art. 7 Abs. 1 Satz 1 des Bundesgesetzes vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG), welches vorliegend in Verbindung mit den damaligen Ausführungserlassen intertemporalrechtlich noch Anwendung findet (vgl. Art. 126 Abs. 1 AuG [SR 142.20]), Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung hat. Ein entsprechender Anspruch ergibt sich auch aus dem in Art. 8 Ziff. 1 EMRK und <ref-law> garantierten Recht auf Achtung des Familienlebens, da die familiäre Beziehung intakt ist und tatsächlich gelebt wird (<ref-ruling> E. 3.1 S. 285 f.; <ref-ruling> E. 5.3.1 S. 211, je mit Hinweisen). Die Frage, ob der Anspruch erloschen ist, weil - wie die Vorinstanz angenommen hat - ein Ausweisungsgrund vorliegt, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1.5 S. 150 mit Hinweis). Auf die Beschwerde ist einzutreten.
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 2.2 S. 246).
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Der Anspruch des ausländischen Ehegatten eines Schweizer Bürgers auf Erteilung und Verlängerung der Aufenthaltsbewilligung erlischt, wenn ein Ausweisungsgrund vorliegt (Art. 7 Abs. 1 Satz 3 ANAG), d.h. unter anderem wenn der Ausländer wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde (Art. 10 Abs. 1 lit. a ANAG). Die Ausweisung bzw. Nichterteilung der Aufenthaltsbewilligung rechtfertigt sich, wenn die nach Art. 11 Abs. 3 ANAG bzw. Art. 8 Ziff. 2 EMRK gebotene Interessenabwägung die Massnahme als verhältnismässig erscheinen lässt (vgl. <ref-ruling> E. 2a S. 523). Dabei sind namentlich die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit sowie die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. Art. 16 Abs. 3 der vormaligen Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer [ANAV]; <ref-ruling> E. 3 und 4 S. 216 ff.).
Eine vergleichbare Interessenabwägung setzt im Übrigen gemäss Art. 8 Ziff. 2 EMRK auch ein Eingriff in das Recht auf Achtung des Familienlebens voraus (<ref-ruling> E. 2 S. 5 f. mit Hinweisen). Unter diesem Gesichtswinkel ist namentlich zu fragen, ob den nahen Familienangehörigen zugemutet werden kann, dem Ausländer, der keine Bewilligung erhält, ins Ausland zu folgen. Die Zumutbarkeit der Ausreise für nahe Familienangehörigen ist umso eher zu bejahen, als sein Verhalten seinen Aufenthalt in der Schweiz als unerwünscht erscheinen lässt. Eine allfällige Unzumutbarkeit der Ausreise ist mitabzuwägen, führt aber nicht für sich allein zur Unzulässigkeit einer Bewilligungsverweigerung (<ref-ruling> E. 4b S. 131; <ref-ruling> E. 2 S. 6).
2.2 Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung ist die vom Strafrichter verhängte Strafe (<ref-ruling> E. 3.1 S. 216; <ref-ruling> E. 4b S. 14). Bei einem mit einem Schweizer Bürger verheirateten Ausländer, der erstmals um eine Bewilligung ersucht oder nach bloss kurzer, ordnungsgemässer Aufenthaltsdauer deren Erneuerung beantragt, nimmt das Bundesgericht an, dass die Grenze von der an in der Regel selbst dann keine Bewilligung mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar erscheint, bei einer Freiheitsstrafe von zwei Jahren liegt. In dieser Situation bedarf es praxisgemäss aussergewöhnlicher Umstände, um die Erteilung einer Aufenthaltsbewilligung dennoch zu rechtfertigen ("Reneja"-Praxis: <ref-ruling> ff.), auch wenn es sich bei der Zweijahresregel um keine feste Grenze handelt, die im Einzelfall nicht über- oder unterschritten werden könnte (vgl. 130 II 176 E. 4.1 S. 185 mit Hinweisen). Entscheidend sind in jedem Fall die einander gegenüberstehenden öffentlichen und privaten Interessen (BGE <ref-ruling> E. 4b S. 14).
3. 3.1 Gemäss Art. 10 Abs. 1 lit. a ANAG kann ein Ausländer aus der Schweiz oder aus einem Kanton ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde. Der erwähnte Ausweisungsgrund setzt einen Schuldspruch wegen einer Straftat voraus, welche nach strafrechtlichen Gesichtspunkten als Verbrechen oder Vergehen einzustufen ist (vgl. dazu im Einzelnen <ref-ruling> E. 3 S. 524 ff.). Nicht vorausgesetzt wird demgegenüber, dass der Schuldspruch notwendigerweise in einem schweizerischen Strafurteil enthalten sein muss. Nach der Rechtsprechung kann vielmehr auch eine Verurteilung im Ausland Anwesenheitsansprüche im Sinne von Art. 7 und 17 ANAG zum Erlöschen bringen (vgl. etwa die Urteile 2C_609/2008 vom 8. Januar 2009, E. 2 und 3; 2C_381/2008 vom 14. Januar 2009, E. 2; 2A.57/2000 vom 17. April 2000, E. 3; 2A.127/1994 vom 17. Oktober 1995, E. 3a; 2A.315/2005 vom 18. Oktober 2005, E. 3.2.1; ferner: <ref-ruling> E. 4.3.1 S. 29). In Zusammenhang mit dem Ausweisungsgrund von Art. 10 Abs. 1 lit. a ANAG muss dies jedenfalls dann gelten, wenn zum einen die in Frage stehenden Delikte, derentwegen die Verurteilung im Ausland erfolgte, nach Massgabe der entsprechenden schweizerischen Strafnormen als Verbrechen oder Vergehen im Sinne von <ref-law> (in der seit 1. Januar 2007 gültigen Fassung) zu qualifizieren wären, und zum anderen der Schuldspruch in einem Staat erfolgt ist, in welchem die Beachtung der grundlegenden rechtsstaatlichen Verfahrensgrundsätze und Verteidigungsrechte im Strafprozess als garantiert erscheint. Letzteres ist bei Ländern wie Deutschland ohne weiteres anzunehmen.
Vorliegend erfolgte die Verurteilung des Beschwerdeführers, wie sich aus dem Auszug aus dem deutschen Zentralstrafregister ergibt, wegen Vergewaltigung und Betrug, wobei es sich um Straftaten handelt, welche in der Schweiz als Verbrechen zu qualifizieren sind (vgl. Art. 190 bzw. <ref-law>). Was der Beschwerdeführer gegen das betreffende Strafverfahren vorbringt, namentlich dass er von einem Anwalt vertreten worden sei, welcher seine Interessen nicht gehörig wahrgenommen habe, ist nicht geeignet, das betreffende Strafurteil, welches in Rechtskraft erwachsen ist, als in Verletzung elementarer Verfahrensgarantien ergangen darzustellen. Dies umso weniger, als der Beschwerdeführer dieses Urteil nicht zu den Akten gegeben hat und auch nie näher dargelegt hat, was genau ihm strafrechtlich vorgeworfen worden ist. Im Übrigen hält die Vorinstanz mit Recht fest, dass allfällige Mängel des erstinstanzlichen Strafverfahrens vom Beschwerdeführer im Rahmen eines Rechtsmittel- oder Revisionsverfahrens hätten geltend gemacht werden müssen. Auf die vom Beschwerdeführer gegenüber seinem damaligen Verteidiger erhobenen Vorwürfe, welche grösstenteils auf nicht näher substantiierten Behauptungen oder wenig aussagekräftigen Dokumenten beruhen, brauchte das Verwaltungsgericht nicht näher einzugehen. Eine Verletzung des rechtlichen Gehörs liegt nicht vor.
Nach dem Gesagten ist das Vorliegen eines Ausweisungsgrundes im Sinne von Art. 10 Abs. 1 lit. a ANAG zu bejahen.
3.2 Die Vorbringen des Beschwerdeführers vermögen auch die von der Vorinstanz in vertretbarer Weise vorgenommene Interessenabwägung nicht in Frage zu stellen.
Der Beschwerdeführer ist in Deutschland zu einer Freiheitsstrafe von drei Jahren und drei Monaten verurteilt worden. Dass er wegen der begangenen Straftaten - Vergewaltigung und Betrug - in der Schweiz möglicherweise milder bestraft worden wäre, wie in der Beschwerde behauptet wird, ändert nichts. Die entsprechenden Straftatbestände des schweizerischen Strafgesetzbuches liessen jedenfalls vom Strafrahmen her durchaus ein Strafmass in ähnlicher Höhe zu. Mit Blick auf die Art der Delikte, die ausgefällte hohe Freiheitsstrafe und den Umstand, dass er deswegen - wiewohl seine (mittlerweile erwachsenen) Kinder aus erster Ehe dort leben - dauerhaft aus Deutschland ausgewiesen worden ist, kann ohne weiteres auf ein in fremdenpolizeilicher Hinsicht schweres Verschulden geschlossen werden. Dass die betreffenden Straftaten im Zeitpunkt des Urteils, wie weiter vorgebracht wird, bereits zehn Jahre zurückgelegen hätten, vermag den Beschwerdeführer nicht entscheidend zu entlasten.
Zudem verhielt sich der Beschwerdeführer auch nach seiner Einreise in die Schweiz keineswegs klaglos: Am 4. November 2004 wurde er aufgrund des Verschweigens seiner Vorstrafen wegen Zuwiderhandlung gegen fremdenpolizeiliche Vorschriften mit einer Busse von Fr. 500.-- bestraft. Dieses Verhalten diente, wie die Vorinstanz zu Recht annehmen durfte, dazu, die Aufenthaltsbewilligung durch falsche Angaben und wissentliches Verschweigen zu erschleichen. Sodann war er am 19. Januar 2006 an einer Schlägerei in einem Sauna-Club beteiligt; die gegen ihn und einen Dritten wegen einfacher Körperverletzung eingeleitete Strafuntersuchung wurde in der Folge zwar wegen Rückzugs des Strafantrags eingestellt. Das Vorgefallene offenbart aber eine gewisse Gewaltbereitschaft des Beschwerdeführers.
Mit Blick auf die genannten Umstände durfte das Verwaltungsgericht ohne Verletzung von Bundesrecht von einer anhaltend erheblichen kriminellen Energie des Beschwerdeführers und einem entsprechend gewichtigen Fernhalteinteressen ausgehen.
3.3 Den öffentlichen Interessen sind die privaten Interessen des Beschwerdeführers und seiner Angehörigen an einem Verbleib in der Schweiz gegenüberzustellen. Für den Beschwerdeführer selber, welcher sich erst seit 2004 (mit einer bis Februar 2005 gültigen Aufenthaltsbewilligung) in der Schweiz aufhält und hier nur als oberflächlich integriert gilt, erscheint die Rückkehr ins Heimatland, in welches er nach seiner Ausweisung aus Deutschland im Mai 2003 für fast ein Jahr zurückkehrte und wo auch einige seiner Verwandten leben, ohne weiteres zumutbar, auch wenn die Erwerbsmöglichkeiten für ihn hierzulande möglicherweise etwas besser sind.
Demgegenüber dürfte es für die Ehefrau des Beschwerdeführers, welche ursprünglich aus Russland stammt und seit 1995 in der Schweiz weilt, mit gewissen Schwierigkeiten verbunden sein, ihrem Ehemann in ein Land zu folgen, welches sie nach eigenen Angaben lediglich von einem gemeinsamen Ferienaufenthalt her kennt. Zudem lebt auch ihr inzwischen volljähriger Sohn aus einer früheren Beziehung (geb. 1986) in der Schweiz. Die Ehefrau musste jedoch damit rechnen, dass sie die seit April 2006 bestehende eheliche Gemeinschaft mit dem Beschwerdeführer nicht ohne weiteres auf Dauer wird hier leben können, zumal ihm das Migrationsamt die Verlängerung der Aufenthaltsbewilligung aufgrund der im Ausland begangenen Delikte bereits im November 2004 verweigert hatte. Der Ehefrau war denn auch bekannt, dass ihr Ehemann im Gefängnis gewesen war. Unter diesen Umständen erscheint es auch für sie zumutbar, dem Beschwerdeführer ins Heimatland zu folgen oder aber die eheliche Gemeinschaft im Rahmen von Besuchsaufenthalten zu pflegen.
3.4 Damit hält die im angefochtenen Urteil vorgenommene Interessenabwägung bundesgerichtlicher Prüfung stand. Die Bewilligungsverweigerung erweist sich als verhältnismässig und mithin bundesrechts- und konventionskonform.
4. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet abzuweisen.
Entsprechend dem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (<ref-law>). Parteientschädigungen sind nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Regierungsrat (Staatskanzlei) und dem Verwaltungsgericht (4. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. Januar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Merkli Moser