Sachverhalt:
A.
A.a. Der 1957 geborene A._ hatte sich am 30. August 2012 unter Hinweis auf Rücken- und Knieschmerzen erstmals zum Bezug von Leistungen bei der Invalidenversicherung angemeldet. Im Wesentlichen gestützt auf die Gutachten der Medizinische Abklärungsstelle Bern ZVMB GmbH (nachfolgend: MEDAS) vom 21. Februar 2014 und 29. Juni 2016 hatte die IV-Stelle Nidwalden einen Rentenanspruch mit - unangefochten in Rechtskraft erwachsener - Verfügung vom 25. August 2016 verneint.
A.b. Am 29. März 2017 meldete sich A._ erneut bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle holte unter anderem ein Verlaufsgutachten bei der MEDAS vom 22. Januar 2018 ein. Nach Durchführung des Vorbescheidverfahrens lehnte sie einen Anspruch auf Leistungen wiederum ab (Verfügung vom 28. Mai 2018).
B.
Das Verwaltungsgericht des Kantons Nidwalden wies die dagegen erhobene Beschwerde ab (Entscheid vom 29. April 2019).
C.
A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Rechtsbegehren, in Aufhebung des kantonalgerichtlichen Entscheids sei die Sache zur erneuten Beurteilung an das Verwaltungsgericht zurückzuweisen; eventuell sei ihm mindestens eine Viertelsrente zuzusprechen.
Die IV-Stelle schliesst auf Abweisung der Beschwerde. Das kantonale Gericht und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 f. BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dennoch prüft es - offensichtliche Fehler vorbehalten - nur die in seinem Verfahren gerügten Rechtsmängel (Art. 42 Abs. 1 f. BGG; <ref-ruling> E. 2.2.1 S. 389). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann ihre Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
1.2. Die gerichtlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit bzw. deren Veränderung in einem bestimmten Zeitraum beziehen sich grundsätzlich auf Tatfragen (<ref-ruling> E. 3.2 S. 397 ff.). Gleiches gilt für die konkrete Beweiswürdigung. Eine Sachverhaltsfeststellung ist nicht schon dann offensichtlich unrichtig, wenn sich Zweifel anmelden, sondern erst, wenn sie eindeutig und augenfällig unzutreffend ist. Eine offensichtlich unrichtige Sachverhaltsfeststellung weist damit die Tragweite von Willkür auf. Es liegt noch keine offensichtliche Unrichtigkeit vor, nur weil eine andere Lösung ebenfalls in Betracht fällt, selbst wenn diese als die plausiblere erscheint. Eine Sachverhaltsfeststellung ist etwa dann offensichtlich unrichtig, wenn das kantonale Gericht den Sinn und die Tragweite eines Beweismittels offensichtlich falsch eingeschätzt, ohne sachlichen Grund ein wichtiges und für den Ausgang des Verfahrens entscheidendes Beweismittel nicht beachtet oder aus den abgenommenen Beweisen unhaltbare Schlüsse gezogen hat. Solche Mängel sind in der Beschwerde aufgrund des strengen Rügeprinzips (vgl. <ref-law>) klar und detailliert aufzuzeigen (<ref-ruling> E. 4.2 S. 53 mit Hinweisen; Urteil 9C_752/2018 vom 12. April 2019 E. 1.2).
2.
Streitig und zu prüfen ist, ob das kantonale Gericht Bundesrecht verletzte, indem es die leistungsablehnende Verfügung der IV-Stelle vom 28. Mai 2018 schützte.
3.
3.1. Im angefochtenen Entscheid werden die Bestimmungen und Grundsätze zur Erwerbsunfähigkeit (<ref-law>), zur Invalidität (<ref-law> i.V.m. <ref-law>), zum Anspruch auf eine Invalidenrente (<ref-law>) sowie zur Beweiswürdigung und zum Beweiswert medizinischer Berichte und Gutachten (vgl. <ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3a S. 352) zutreffend dargelegt. Darauf wird verwiesen.
3.2.
3.2.1. Ergänzend ist im Zusammenhang mit der Prüfung einer Neuanmeldung auf Art. 87 Abs. 3 in Verbindung mit Abs. 2 IVV und die dazu ergangene Rechtsprechung aufmerksam zu machen, wonach - bei Glaubhaftmachung einer (hier interessierenden) Änderung des Invaliditätsgrades in anspruchserheblicher Weise - analog wie bei einem Revisionsfall nach <ref-law> vorzugehen ist (<ref-ruling> E. 2.3 S. 10 f.; <ref-ruling> E. 3 S. 132 f.).
3.2.2. Vergleichszeitpunkte für die Überprüfung, ob eine anspruchsrelevante Veränderung eingetreten ist, bilden im vorliegenden Fall fraglos die Zeitpunkte des Erlasses der beiden rentenablehnenden Verfügungen vom 25. August 2016 und vom 28. Mai 2018.
4.
Im vorinstanzlichen Entscheid wurde nach einlässlicher und sorgfältiger Würdigung der medizinischen Unterlagen festgestellt, auf das Verlaufsgutachten vom 22. Januar 2018 könne abgestellt werden, weshalb davon auszugehen sei, dass in einer körperlich leichteren Verweistätigkeit eine 100%ige Arbeitsfähigkeit bestehe. Gestützt darauf sei, was die entsprechenden erwerblichen Auswirkungen anbelange, ein erzielbares Einkommen ohne invalidisierenden Gesundheitsschaden (Valideneinkommen) von Fr. 82'520.- mit einem Invalideneinkommen von Fr. 61'183.- zu vergleichen, woraus kein rentenbegründender Invaliditätsgrad resultiere.
5.
Die in der Beschwerde dagegen erhobenen Rügen führen zu keinem anderen Ergebnis, wie sich nachfolgend zeigt.
5.1.
5.1.1. Wie schon vor der Vorinstanz macht der Versicherte auch vor Bundesgericht geltend, auf das Gutachten vom 22. Januar 2018 könne schon deshalb nicht abgestellt werden, weil es - nachdem die Begutachtung bereits im Juni 2017 stattgefunden habe - erst im Januar 2018 erstellt worden sei. Damit habe die Gutachterstelle gegen die Vereinbarung zwischen dem BSV und den anerkannten MEDAS-Begutachtungsstellen verstossen, die eine Ablieferungsfrist von 110 Kalendertagen vorsehe. Ausserdem habe der Gesundheitszustand im Januar 2018 längst nicht mehr mit den Befunden im Juli 2017 übereingestimmt.
Nicht eingehaltene Fristbestimmungen aus einer Vereinbarung zwischen dem BSV und den Begutachtungsstellen führen nicht schon für sich allein dazu, dass eine Expertise nicht mehr als beweiswertig zu betrachten wäre (vgl. Urteil 8C_549/2013 vom 4. Dezember 2013 E. 3.1.1). Solange sich der Gesundheitszustand zwischen Begutachtung und Ablieferung des Gutachtens nicht verändert hat, besteht allein wegen der Verzögerung kein Grund, den Beweiswert in Frage zu stellen. Der Beschwerdeführer vermag denn auch keine Gründe zu benennen, die eine gesundheitliche Verschlechterung in diesem Zeitraum untermauern könnten. Die pauschale Behauptung, der Gesundheitszustand würde sich seit mehreren Jahren stetig verschlechtern, konnte zudem von den medizinischen Fachpersonen insgesamt gerade nicht bestätigt werden. Die in der Beschwerde genannten Berichte der behandelnden Ärzte vermögen nichts anderes zu belegen, wie schon die Vorinstanz ausgeführt hat. Der rheumatologische Bericht vom 18. Juni 2018, auf den sich der Versicherte in diesem Zusammenhang beruft und im vorinstanzlichen Verfahren eingereicht haben will, befindet sich im Übrigen gar nicht bei den Akten und wird weder in seinem Beweismittelverzeichnis zur Beschwerde ans kantonale Gericht noch in jenem zur Replik genannt. Dass zwischen der Erteilung und der Erledigung eines Begutachtungsauftrags einige Zeit vergeht, ist sodann gerade bei polydisziplinären Expertisen, welche Teilgutachten verschiedener medizinischer Fachrichtungen und eine gesamthafte Würdigung erfassen, nicht unüblich. Daran ändert nichts, dass es sich im vorliegenden Fall um ein Verlaufsgutachten handelt. Der Beschwerdeführer scheint zu verkennen, dass sich die Fachpersonen auch bei einer zweiten oder dritten Begutachtung derselben Person jeweils wieder aufs Neue in die Krankengeschichte einarbeiten und die seitherige Entwicklung bis zum aktuellen Zustand gleichermassen gründlich abklären müssen. Jedenfalls kann aus der hier verstrichenen Zeit - mit der Vorinstanz - nicht gefolgert werden, auf die Expertise vom 22. Januar 2018 könne nicht abgestellt werden.
5.1.2. Des Weiteren rügt der Versicherte, das kantonale Gericht habe nicht berücksichtigt, dass die Gutachter im Vergleich zur Expertise aus dem Jahr 2016 unter der Rubrik "mit Auswirkung auf die Arbeitsfähigkeit" zusätzliche Diagnosen aufgeführt hätten. Da diese hinzugetretenen Diagnosen also einen wesentlichen Einfluss auf die noch zumutbaren Tätigkeiten hätten, bestehe ein offensichtlicher Widerspruch, soweit im orthopädischen (Teil-) Gutachten aus dem Jahr 2018 von einer leichten Verbesserung des Gesundheitszustandes ausgegangen werde. Da die Vorinstanz auf dieses Argument nicht eingegangen sei, habe sie das rechtliche Gehör bzw. die gesetzliche Begründungspflicht verletzt. Ausserdem habe sich der orthopädische Experte mit den Befunden gemäss Abklärungsbericht der Dr. med. B._, Rheumatologie FMH, vom 28. Februar 2017 - namentlich mit der Einschätzung, dass sich der gesundheitliche Zustand seit der Begutachtung 2016 verschlechtert habe - nicht begründet befasst. Deshalb komme dem Gutachten auch materiell kein Beweiswert zu. Das kantonale Gericht sei zudem nicht auf den (vorinstanzlich eingereichten) Austrittsbericht der Klinik für Orthopädie/Traumatologie, Spital C._, vom 20. September 2018 und die Stellungnahme der Dr. med. B._ vom 2. November 2018 eingegangen. Aus diesen ergäben sich zusätzliche Befunde, die im Gutachten weder erhoben noch beurteilt worden seien, sodass auf die darin enthaltene Einschätzung der Arbeitsfähigkeit nicht abgestützt werden könne.
Wie bereits im angefochtenen Entscheid ausgeführt wird, bildet nicht die Anzahl der Diagnosen, die unter der Rubrik "mit Einfluss auf die Arbeitsfähigkeit" aufgelistet sind, den Ausschlag für das Ausmass der Einschränkung der Arbeitsfähigkeit, sondern der Schweregrad der Befunde sowie die konkreten Auswirkungen auf die Leistungsfähigkeit. Ausserdem erscheint das Abstellen auf das MEDAS-Gutachten vom 22. Januar 2018 auch im Vergleich mit dem Bericht der Dr. med. B._ vom 28. Februar 2017 nicht als willkürlich. Die Rheumatologin hat zwar von einer Verschlechterung des Zustandes seit 2015 mit Zunahme des lumbo- und zervikoradikulären Syndroms, der degenerativen Veränderungen beider Knie und der Adipositas berichtet. Dem orthopädischen Experten war diese Einschätzung bekannt, wie sich aus dem Gutachten ergibt. Im Gegensatz zur behandelnden Rheumatologin nahm er differenziert Stellung zur Befundkonsistenz und bezog namentlich auch die Beobachtungen bei der Messung des passiven Bewegungsumfangs (Halswirbelsäule, Schultergelenk, Lendenwirbelsäule, Arme und Beine) und bei der manuellen Untersuchung sowie die objektiv festgestellte fehlende Muskelminderung in seine Beurteilung mit ein. Wenn er deshalb in einer den gesundheitlichen Einschränkungen angepassten Erwerbstätigkeit - im Ergebnis unverändert im Vergleich zur Sachlage bei der ersten Rentenablehnung im Jahr 2016 - eine 100%ige Arbeitsfähigkeit attestierte, so kann dies nicht als offensichtlich unrichtig gelten. Auf die im vorinstanzlichen Verfahren eingereichten Berichte, die die Entwicklung nach Erlass der Verfügung vom 28. Mai 2018 betreffen, musste das kantonale Gericht sodann schon deshalb nicht eingehen, weil vorliegend lediglich der Leistungsanspruch basierend auf dem Gesundheitszustand, wie er sich bis zum 28. Mai 2018 darstellte, zur Debatte stehen kann.
5.1.3. Soweit der Beschwerdeführer vorbringt, auch auf das psychiatrische Teilgutachten 2018 hätte das kantonale Gericht nicht abstellen dürfen, kann ihm ebenfalls nicht gefolgt werden. Entgegen seiner Behauptung setzte sich der psychiatrische Experte mit den anderslautenden Diagnosen der behandelnden Fachpersonen auseinander und ging sogar insoweit mit ihnen einig, dass er eine anfängliche Anpassungsstörung und eine leichte depressive Störung als möglich erachtete. Im Untersuchungszeitpunkt war die mögliche psychische Alteration nach seiner Einschätzung allerdings weitgehend remittiert, so dass er keine psychiatrische Diagnose mit Auswirkung auf die Arbeitsfähigkeit stellen konnte.
5.1.4. Wenn die Vorinstanz unter anderem mit Blick auf die Angaben der orthopädischen und psychiatrischen Experten zum Schluss gelangte, das MEDAS-Gutachten vom 22. Januar 2018 sei in Kenntnis der Vorakten ergangen und die Experten hätten sich mit den Einschätzungen der behandelnden Ärzte genügend auseinandergesetzt, und gestützt darauf eine 100%ige Arbeitsfähigkeit in einer leidensangepassten Tätigkeit feststellte, so ist dies nicht zu beanstanden. Denn eine vertiefte Auseinandersetzung mit jedem einzelnen Bericht ist nicht erforderlich, wenn sich - wie hier - insgesamt ein vollständig und schlüssig ermitteltes Bild des Gesundheitszustandes und der Entwicklung seit der Begutachtung im Jahr 2016 ergibt (vgl. Urteil 8C_642/2011 vom 14. Februar 2012 E. 5.2).
Den von Versicherungsträgern im Verfahren nach <ref-law> eingeholten, den Anforderungen der Rechtsprechung entsprechenden Gutachten externer Spezialärzte darf Beweiswert zuerkannt werden, solange nicht konkrete Indizien gegen die Zuverlässigkeit der Expertise sprechen (<ref-ruling> E. 4.4 S. 470; Urteil 9C_18/2019 vom 14. Juni 2019 E. 2.2 mit Hinweisen). Solche vermag der Beschwerdeführer nicht aufzuzeigen. Ein Administrativgutachten ist denn auch nicht stets dann in Frage zu stellen und zum Anlass weiterer Abklärungen zu nehmen, wenn behandelnde Ärzte zu einem anderen Ergebnis gelangen; vorbehalten bleiben Fälle, in denen sich eine abweichende Beurteilung aufdrängt, weil sie wichtige Aspekte benennen, die im Rahmen der Begutachtung unerkannt oder ungewürdigt geblieben sind (vgl. statt vieler SVR 2017 IV Nr. 49 S. 148; 9C_119/2020 vom 18. Mai 2010 E. 3.2.3). Inwiefern solche Aspekte aus den medizinischen Akten hervorgingen, ist weder ersichtlich noch in der Beschwerde rechtsgenüglich dargetan.
5.2. Beim Invalideneinkommen, das dem Einkommensvergleich zugrunde gelegt wird, möchte der Versicherte anstelle des von der IV-Stelle berücksichtigten 10%igen Leidensabzugs einen solchen von 25 % vornehmen. Dies begründet er mit dem Alter, seiner mittlerweile langjährigen behinderungsbedingten Arbeitsabsenz, sprachlichen Problemen und der beschränkten beruflichen Erfahrung. Weiterungen zur Frage der Höhe des leidensbedingten Abzugs erübrigen sich hier allerdings schon deshalb, weil - wie von der Vorinstanz zutreffend festgehalten - auch der Maximalabzug von 25 % (<ref-ruling> E. 5b/cc S. 80) zu einem rentenausschliessenden Invaliditätsgrad (von 38 %) führen würde. Von einer wirtschaftlich nicht verwertbaren Resterwerbsfähigkeit kann schliesslich ebenfalls nicht ausgegangen werden.
6.
Zusammenfassend ist die vorinstanzliche Sachverhaltsfeststellung unter Einschluss der Beweiswürdigung weder offensichtlich unrichtig (unhaltbar, willkürlich: <ref-ruling> E. 6.3 S. 375; <ref-ruling> E. 8.1 S. 153), noch beruht sie auf einer (anderweitigen) Rechtsverletzung; sie bleibt daher für das Bundesgericht verbindlich (E. 1.1 hiervor). Damit durfte das kantonale Gericht von ergänzenden medizinischen Abklärungen absehen, ohne Bundesrecht zu verletzen (antizipierende Beweiswürdigung; <ref-ruling> E. 5.3 S. 236; <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 4b S. 94). Die Beschwerde ist unbegründet.
7.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdeführer die Gerichtskosten zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht Nidwalden, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 19. Juli 2020
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Berger Götz