Sachverhalt:
A.
Der 1986 geborene kosovarische Staatsangehörige A._ reiste im Jahr 2005 illegal in die Schweiz ein, weswegen er durch die Staatsanwaltschaft Winterthur mit Strafbefehl vom 31. März 2005 mit einer bedingten Gefängnisstrafe von 45 Tagen sanktioniert wurde. Am 3. April 2005 wurde er aus der Schweiz ausgeschafft.
Am 17. August 2010 heiratete A._ eine in der Schweiz niedergelassene kosovarische Landsfrau. Er reiste daraufhin im Juni 2011 in die Schweiz ein und erhielt hier eine bis 16. Juni 2012 gültig gewesene Aufenthaltsbewilligung. Nachdem er bereits Anfang 2012 aus der ehelichen Wohnung ausgezogen war, lehnte der damals zuständige Migrationsdienst des Kantons Bern am 22. Februar 2013 die Verlängerung der Aufenthaltsbewilligung von A._ ab und er setzte ihm eine Frist bis zum 30. April 2013, um die Schweiz zu verlassen. In der Folge liess A._ die Ehe mit seiner Landsfrau am 5. März 2013 im Kosovo scheiden, dies in Abwesenheit beider Gatten. Wenige Tage später, am 15. März 2013, ersuchte A._ den Migrationsdienst um Aufschub der Wegweisung, zumal er nun beabsichtige, die Schweizerin B._ zu heiraten. Nachdem der Migrationsdienst diesem Ersuchen nicht entsprochen hatte, reiste A._ am 28. April 2013 in den Kosovo aus.
Am 20. Februar 2015 heiratete A._ im Kosovo die 1970 geborene, d.h. 16 Jahre ältere schweizerische Staatsangehörige B._.
B.
Am 27. März 2015 ersuchte er das Migrationsamt des Kantons Zürich um Erteilung einer Einreise- und Aufenthaltsbewilligung zwecks Verbleib bei der Gattin.
Mit Verfügung vom 9. Oktober 2015 wies das Migrationsamt das Gesuch ab. Die von den Betroffenen hiergegen ergriffenen kantonalen Rechtsmittel wurden von der Sicherheitsdirektion des Kantons Zürich (Rekursentscheid vom 25. Oktober 2016) sowie vom Verwaltungsgericht des Kantons Zürich (Urteil vom 11. Januar 2017) abgewiesen. Sämtliche kantonalen Instanzen gelangten zum Schluss, dass A._ die Ehe einzig deshalb eingegangen sei, um sich in der Schweiz erneut ein Aufenthaltsrecht zu verschaffen.
C.
Mit Eingabe vom 14. Februar 2017 führen A._ und B._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen im Wesentlichen, A._ eine Einreiseerlaubnis und anschliessend eine Aufenthaltsbewilligung zu erteilen.
Die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich verzichten auf Vernehmlassung.
Mit Schreiben vom 12. April 2017 wurden den Beschwerdeführern die Stellungnahmen der Vorinstanzen mitgeteilt. Innert der hierfür angesetzten Frist erfolgte keine weitere (fakultative) Eingabe der Beschwerdeführer.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit bzw. die Zulässigkeit des Rechtsmittels von Amtes wegen (<ref-law>) und mit freier Kognition (<ref-ruling> E. 1 S. 476).
Nach <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen ausgeschlossen, auf deren Erteilung weder das Bundes- noch das Völkerrecht einen Rechtsanspruch einräumen. Der Ehemann einer Schweizer Bürgerin hat einen grundsätzlichen Anspruch auf Erteilung der Aufenthaltsbewilligung (Art. 42 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]; vgl. E. 2.1 hiernach). Die Schweizer Ehefrau des Ausländers kann sich zudem auf den von Art. 8 EMRK (bzw. <ref-law>) gewährleisteten Anspruch auf Familienleben berufen. Ob ihrem Gatten die Bewilligung tatsächlich zu erteilen ist, bildet nicht Eintretensfrage, sondern Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S. 150).
Die Beschwerde wurde unter Einhaltung der gesetzlichen Frist (<ref-law>) und Form (<ref-law>) von zwei durch die Entscheidung besonders berührten Personen mit einem schutzwürdigen Interesse an deren Aufhebung oder Änderung (<ref-law>) eingereicht. Sie richtet sich gegen einen kantonal letztinstanzlichen Endentscheid eines oberen Gerichts (Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Auf das Rechtsmittel kann daher eingetreten werden.
2.
2.1. Nach Art. 42 Abs. 1 AuG hat der Ehemann einer Schweizer Bürgerin grundsätzlich Anspruch auf Erteilung der Aufenthaltsbewilligung. Gemäss Art. 51 Abs. 1 lit. a AuG erlöscht dieser Anspruch allerdings, wenn er rechtsmissbräuchlich geltend gemacht wird, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen. Erfasst wird davon insbesondere die sog. Schein- oder Ausländerrechtsehe. Ihr Vorliegen darf nicht leichthin angenommen werden und ist nicht bereits dann gegeben, wenn ausländerrechtlicheMotive für den Eheschluss mitentscheidend waren (vgl. <ref-ruling> E. 2.2 S. 151). Ein Bewilligungsanspruch entfällt vielmehr erst dann, wenn die Ehe einzig geschlossen wurde, um die ausländerrechtlichen Bestimmungen zu umgehen, indem zumindest einer der Ehegatten nie eine dauerhafte Lebensgemeinschaft begründen wollte (<ref-ruling> E. 4a S. 55; <ref-ruling> E. 2 S. 294 ff.; <ref-ruling> E. 2 S. 2 ff.; Urteil 2C_1027/2016 vom 10. Mai 2017 E. 3.1).
2.2. Ob eine Scheinehe geschlossen wurde bzw. ob die Ehe bloss formell besteht, entzieht sich in der Regel dem direkten Beweis und ist nur durch Indizien zu erstellen (<ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweisen). Solche Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten). So oder anders handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. <ref-law>). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften oder sei rechtsmissbräuchlich (<ref-ruling> E. 2.3 S. 152 mit Hinweisen; Urteile 2C_154/2015 vom 17. März 2015 E. 2.2).
2.3. Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass jedenfalls ein Ehegatte nicht eine eigentliche Lebensgemeinschaft führen will, sondern die Ehe nur aus ausländerrechtlichen Überlegungen geschlossen hat. Zu diesen Indizien zählen namentlich folgende Umstände: Die Tatsache, dass die nachzuziehende Person von einer Wegweisung bedroht ist oder ohne Heirat keine Aufenthaltsbewilligung erlangen kann; das Vorliegen eines erheblichen Altersunterschieds zwischen den Ehegatten; die Umstände des Kennenlernens und der Beziehung, so etwa eine kurze Bekanntschaft vor der Heirat oder geringe Kenntnisse eines Ehegatten über den anderen; die Vereinbarung einer Bezahlung für die Heirat; die Tatsache, dass die Ehegatten nie eine Wohngemeinschaft aufgenommen haben (<ref-ruling> E. 3.1 S. 152; Urteile 2C_1027/2016 vom 10. Mai 2017 E. 3.1; 2C_154/2015 vom 17. März 2015 E. 2.3).
3.
3.1. Das Verwaltungsgericht führte in diesem Zusammenhang aus, der Beschwerdeführer 1 habe sich bereits im Jahr 2005 illegal bei Familienangehörigen in der Schweiz aufgehalten und sei in der Folge ausgeschafft worden, weswegen ihm schon deshalb habe bewusst sein müssen, dass ihm nur die Heirat mit einer hier aufenthaltsberechtigten Person seinerseits ein Aufenthaltsrecht verschaffe. Im Jahr 2010 habe er dann eine in der Schweiz niederlassungsberechtigte Landsfrau geheiratet, sich aber nach rund einem halben Jahr, Anfang 2012, von der gemeinsamen Wohnadresse abgemeldet. Die damalige Ehefrau habe hierzu ausgeführt, der Beschwerdeführer 1 habe von Anfang an nicht die Absicht gehabt, in der gemeinsamen Wohnung zu leben; seit September 2011 habe er sich dort nur noch eine Nacht aufgehalten. Weiter zog die Vorinstanz in Erwägung, der Beschwerdeführer 1 habe nach der Trennung erst verneint, dass er die Scheidung wolle, doch im Anschluss an die am 22. Februar 2013 verfügte Nichtverlängerung seiner Aufenthaltsbewilligung habe er sich bereits am 5. März 2013 in Abwesenheit beider Gatten im Kosovo scheiden lassen. Am 15. März 2013 habe er schliesslich um Aufschiebung seiner Wegweisung ersucht, weil er und die Beschwerdeführerin 2 die Ehevorbereitung eingeleitet hätten. In einem dem Migrationsamt des Kantons Zürich am 18. Mai 2015 zugegangenen Schreiben der Beschwerdeführerin 2 habe diese vorgebracht, der Beschwerdeführer 1 habe sich erstmals nach ihrer Heiratsbereitschaft erkundigt, nachdem er eine Mitteilung des Migrationsamtes erhalten habe, wobei es sich um das Schreiben vom 31. August 2012 betreffend das rechtliche Gehör zur beabsichtigten Wegweisung handeln dürfte. Dieser Ablauf lasse darauf schliessen, dass der Beschwerdeführer 1 die Ehe mit der Beschwerdeführerin 2 im Wesentlichen eingehen wollte, um seine Wegweisung zu verhindern. Sodann sei der Altersunterschied von 16 Jahren sowie die Tatsache, dass die Beschwerdeführerin 2 bereits zwei Kinder aus einer früheren Beziehung habe, im Kulturkreis des Beschwerdeführers 1 ungewöhnlich und mithin ebenfalls ein Indiz dafür, dass er die Ehe einzig mit dem Zweck einging, wieder ein Aufenthaltsrecht in der Schweiz zu erhalten. Auffallend sei auch, dass sich der Beschwerdeführer 1 anlässlich einer Befragung vom 19. Juni 2015 - knapp vier Monate nach der Hochzeit - nicht an das Heiratsdatum habe erinnern können, was darauf hindeute, dass er dem Ereignis keine grosse Bedeutung zumesse. Zudem wolle er am gleichen Tag Verlobung gefeiert haben, als sich die Gatten gemäss Darstellung der Beschwerdeführerin 2 überhaupt erst kennengelernt hätten. Schliesslich bestünden auch weitere Abweichungen in den Aussagen der Gatten: Während es die Beschwerdeführerin 2 offen gelassen habe, ob gemeinsame Kinder geplant sind, und sie angegeben habe, den Beschwerdeführer 1 insgesamt achtmal im Kosovo besucht zu haben, habe der Beschwerdeführer 1 behauptet, dass ihn seine Gattin "fast 20 mal innerhalb von zwei Jahren" im Kosovo besucht habe, und dass gemeinsame Kinder geplant seien, sobald er in der Schweiz sei. Dies lasse den Eindruck entstehen, dass der Beschwerdeführer 1 versuche, eine Beziehung herbeizureden, die in dieser Form nicht bestehe.
3.2. Die Beschwerdeführer bestreiten den fehlenden Ehewillen des Beschwerdeführers 1 wie auch dessen Absicht, sich durch die Heirat in erster Linie einen Aufenthaltstitel für die Schweiz zu sichern. Sie verweisen darauf, dass sie sich mittlerweile seit fast fünf Jahren kennen und seit der Heirat Ringe tragen würden. Die Beschwerdeführerin 2 sei zudem eine absolut integre Frau mit einwandfreiem Leumund, welche in geordneten finanziellen Verhältnissen lebe. Als der Beschwerdeführer 1 die Schweiz habe verlassen müssen, sei die Beschwerdeführerin 2 mit ihm in den Kosovo mitgereist und sie habe ihn auch regelmässig im Kosovo besucht und dort seine Verwandten kennengelernt. Sie hätten sowohl in der Schweiz auch als im Kosovo viel zusammen unternommen, unter anderem Ausflüge, Restaurantbesuche und Treffen mit Freunden und der Familie. Sodann unterstütze die Beschwerdeführerin 2 den Beschwerdeführer 1 auch regelmässig finanziell. Zudem hätten sie bei den Befragungen sehr weitgehend übereinstimmende und lebensnahe Aussagen gemacht, insbesondere zum Kennenlernen, zur Heirat, zum Beziehungsverlauf, zur Verwandtschaft und zur Vergangenheit des anderen Gatten. Im Zusammenhang mit diesen Vorbringen rügen die Beschwerdeführer eine Verletzung von Bundesrecht, eine willkürliche Sachverhaltsfeststellung sowie eine Verletzung des rechtlichen Gehörs. Ebenfalls eine Verletzung des rechtlichen Gehörs erblicken die Beschwerdeführer im Umstand, dass es die Vorinstanz unterlassen habe, eine langjährige Freundin der Beschwerdeführerin 2 persönlich als Zeugin zu befragen: Diese hätte Auskunft über das Kennenlernen und den Beziehungsverlauf der Beschwerdeführer geben können.
4.
4.1. Die Vorinstanz hat die bundesgerichtliche Praxis zur Annahme einer Scheinehe zutreffend wiedergegeben (E. 2.2 des angefochtenen Entscheids; vgl. auch E. 2.2 und E. 2.3 hiervor) und korrekt auf den hier zu beurteilenden Fall angewandt. Als abstrakte Indizien für das Fehlen eines Ehewillens des Beschwerdeführers 1 durfte das Verwaltungsgericht insbesondere den grossen Altersunterschied zwischen den Beschwerdeführern sowie den Umstand berücksichtigen, dass dem Beschwerdeführer 1 im Zeitpunkt der Aufnahme der Beziehung bzw. des Bekundens seiner Heiratsabsichten die Wegweisung drohte und er zum Verbleiben im Land resp. später zur Rückkehr in die Schweiz der Ehe mit einer schweizerischen Staatsangehörigen oder einer hier niederlassungsberechtigten Person bedurfte.
4.2. Zwar ist richtig, dass diese abstrakten Indizien für sich alleine nicht hinreichend wären, um dem Beschwerdeführer 1 die Bewilligungserteilung zu verweigern (vgl. Urteil 2C_154/2015 vom 17. März 2015). Wie die Vorinstanz zutreffend erkannte, liegen im vorliegenden Fall jedoch darüber hinaus noch zahlreiche konkrete, spezifisch den hier zu beurteilenden Fall betreffende Hinweise dafür vor, dass jedenfalls seitens des Beschwerdeführers 1 kein echter Ehewille vorhanden ist, sondern vielmehr das (erneute) Erlangen einer Aufenthaltsbewilligung im Vordergrund steht:
Namentlich sind dies die Umstände der früheren, nur kurze Zeit andauernden Ehe des Beschwerdeführers 1 mit einer hier niedergelassenen Landsfrau: In einem Schreiben vom Juli 2012 an den damals zuständigen Migrationsdienst des Kantons Bern erklärte diese, sie habe von Anfang an Probleme mit ihm gehabt, seit er in die Schweiz eingereist sei. Er habe nicht in der ehelichen Wohnung bleiben, sondern bei ihren Eltern oder seinem Onkel in Zürich wohnen wollen. Als ihm dies nicht ermöglicht worden sei, habe er für sich entschieden, zwischenzeitlich wieder in den Kosovo zurückzukehren. Dort habe sie ihn einmal besucht. Für sein Einverständnis zu einer Trennung/Scheidung habe er von ihr verlangt, dass sie ihm entweder Fr. 30'000.-- bezahlen oder aber dafür sorgen solle, dass seine Aufenthaltsbewilligung verlängert werde. Eine gemeinsame Zukunft könne sie sich nicht mehr vorstellen, zumal sie realisiert habe, dass er sie nur wegen der Aufenthaltsbewilligung geheiratet habe (Akten des Migrationsamtes S. 162 ff.). Zum Inhalt dieses Schreibens, welches bereits Gegenstand der vorinstanzlichen Urteilsbegründung bildete, äusserte sich der Beschwerdeführer 1 in seiner Eingabe vor Bundesgericht nicht.
Gegenüber der Migrationsbehörde erklärte er jedoch im Juli 2012 nachweislich, er wolle keine Scheidung; seine Frau werde in Kürze wieder mit ihm zusammen sein und sie würden eine Familie gründen (Akten des Migrationsamtes S. 170 f.). Beachtlich sind deshalb auch die im Anschluss an die Verfügung des Migrationsamtes vom 22. Februar 2013 offensichtlich erfolgte plötzliche Meinungsänderung des Beschwerdeführers 1, die am 5. März 2013 ausgesprochene Scheidung von seiner ersten Frau im Abwesenheitsverfahren im Kosovo sowie das kurz darauf verfasste Schreiben des Beschwerdeführers 1 vom 15. März 2013 an den Migrationsdienst des Kantons Bern, mit welchem er unter Hinweis auf eine nunmehr beabsichtigte Eheschliessung mit der Beschwerdeführerin 2 um Aufschiebung seiner Wegweisung ersuchte (Akten des Migrationsamtes S. 190). Mit diesem Schreiben stellte der Beschwerdeführer 1 selbst eine explizite Verbindung zwischen der drohenden Entfernungsmassnahme und der geplanten Ehe mit der Beschwerdeführerin 2 her.
4.3. Was die Beschwerdeführer vorbringen, um diese Auffälligkeiten zu entkräften, überzeugt demgegenüber nicht:
Entgegen ihren Behauptungen lassen sich den Befragungen nicht nur übereinstimmende Angaben entnehmen. Gerade betreffend das Kennenlernen und den Beziehungsverlauf ergeben sich die von der Vorinstanz aufgezeigten Differenzen, wobei der Beschwerdeführer 1 die Beziehung als länger andauernd und die persönlichen Kontakte als intensiver schildert, als dies die Beschwerdeführerin 2 tut. Zudem erscheint es in der Tat als sehr auffällig, dass der Beschwerdeführer 1 anlässlich seiner Befragung vom 19. Juni 2015 durch die Schweizer Botschaft im Kosovo angab, er habe das Datum seiner Hochzeit vergessen (Akten des Migrationsamtes S. 190), obwohl diese zu diesem Zeitpunkt erst vier Monate zurücklag.
Soweit die Beschwerdeführer zudem die Integrität der Beschwerdeführerin 2 und ihre geordneten finanziellen Verhältnisse betonen, ihre Besuche beim Beschwerdeführer 1 im Kosovo hervorheben und auf die finanzielle Unterstützung der Beschwerdeführerin 2 gegenüber dem Beschwerdeführer 1 hinweisen, gehen ihre Ausführungen ins Leere: Die genannten Umstände lassen höchstens Rückschlüsse auf den Ehewillen der Beschwerdeführerin 2 zu. Dieser wird aber von der Vorinstanz überhaupt nicht in Frage gestellt, sondern es wird vom Verwaltungsgericht - im Gegenteil - sogar ausdrücklich anerkannt, dass die Beschwerdeführerin 2 durchaus glaubhaft darlege, eine echte Beziehung eingehen zu wollen. Wie im angefochtenen Entscheid überdies zutreffend festgestellt wurde, kommt es auf den Ehewillen der Beschwerdeführerin 2 aber nicht in entscheidender Weise an: Eine rechtsmissbräuchliche Scheinehe liegt bereits dann vor, wenn der Wille zur Führung einer dauerhaften Lebensgemeinschaft bei einem der Ehepartner fehlt (vgl. E. 2.1 hiervor).
4.4. Bei dieser Sachlage verletzte die Vorinstanz weder Bundes- noch Konventionsrecht, indem sie zum Schluss gelangte, dass es dem Beschwerdeführer 1 an einem echten Ehewillen fehlt und dass er die Ehe im Wesentlichen einging, um sich wieder ein Aufenthaltsrecht in der Schweiz zu verschaffen.
Ebenso wenig war es nötig, vorab die von den Beschwerdeführern angerufene Zeugin persönlich zu befragen: Zum einen bestand die Möglichkeit, deren Beobachtungen in schriftlicher Form ins Verfahren einzubringen. Von dieser Möglichkeit hat die Zeugin denn auch Gebrauch gemacht (vgl. undatiertes Schreiben; Akten des Migrationsamtes S. 360), und es ist nicht ersichtlich, weshalb eine zusätzliche persönliche Befragung noch erforderlich gewesen wäre. Zum andern bezeichnet sich die Zeugin primär als langjährige Freundin der Beschwerdeführerin 2 und macht in erster Linie Angaben zu deren Empfindungen. Wie aufgezeigt, liegt der Ehewillen der Beschwerdeführerin 2 jedoch überhaupt nicht im Streit.
5.
Nach dem Obenstehenden ist die Beschwerde abzuweisen.
Bei diesem Verfahrensausgang tragen die Beschwerdeführer die bundesgerichtlichen Kosten in solidarischer Haftung (<ref-law>). Parteientschädigungen sind nicht geschuldet (Art. 68 Abs. 1-3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten in Höhe von Fr. 2'000.-- werden den Beschwerdeführern in solidarischer Haftung auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, sowie dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 20. Juni 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Zähndler