Sachverhalt:
A. Der 1961 geborene K._ meldete sich am 24. Mai 2006 erneut bei der IV-Stelle des Kantons Solothurn zum Leistungsbezug an, nachdem seine Leistungsbegehren zuvor mehrmals abgewiesen worden waren, letztmals mit Einspracheentscheid vom 4. Januar 2005 vornehmlich gestützt auf ein polydisziplinäres Gutachten der Medizinischen Abklärungsstelle der Universitätsklinik X._ (MEDAS) vom 31. August 2004. Nach ergänzenden medizinischen Abklärungen insbesondere dem Beizug eines polydisziplinären Gutachtens des Instituts Y._, Universitätsspital X._, vom 10. März 2008 verneinte die IV-Stelle nach durchgeführtem Vorbescheidsverfahren einen Rentenanspruch des Versicherten bei einem Invaliditätsgrad von 37 %, sprach ihm jedoch Stellenvermittlung zu (Verfügung vom 18. November 2008).
B. Die dagegen erhobene Beschwerde wies das Versicherungsgericht des Kantons Solothurn mit Entscheid vom 14. Januar 2010 ab.
C. Der Versicherte lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Rechtsbegehren, in Aufhebung des kantonalen Gerichtsentscheides sei ihm mit Wirkung ab 1. Oktober 2004 mindestens eine halbe Rente zuzusprechen.
Die IV-Stelle und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss den Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Mit Blick auf diese Kognitionsregelung ist aufgrund der Vorbringen in der Beschwerde an das Bundesgericht (<ref-law>) nur zu prüfen, ob der angefochtene Gerichtsentscheid in Anwendung der massgeblichen materiell- und beweisrechtlichen Grundlagen (u.a.) Bundesrecht verletzt (<ref-law>), einschliesslich einer allfälligen rechtsfehlerhaften Tatsachenfeststellung (Art. 97 Abs. 1, <ref-law>). Hiezu gehört insbesondere auch die unvollständige (gerichtliche) Feststellung der rechtserheblichen Tatsachen und die Verletzung des Untersuchungsgrundsatzes als einer wesentlichen Verfahrensvorschrift (Urteile 9C_534/2007 vom 27. Mai 2008, E. 1 mit Hinweis auf Ulrich Meyer, Basler Kommentar zum Bundesgerichtsgesetz, Basel 2008, N. 58-61 zu Art. 105; Seiler/von Werdt/Güngerich, Kommentar zum Bundesgerichtsgesetz, Bern 2007, N. 24 zu Art. 97).
2. 2.1 Das kantonale Gericht hat die gesetzlichen Bestimmungen und die von der Rechtsprechung entwickelten Grundsätze, namentlich diejenigen über den Umfang des Rentenanspruchs (<ref-law> in der bis Ende 2007 gültig gewesenen Fassung; nunmehr <ref-law>), die Bemessung des Invaliditätsgrades bei erwerbstätigen Versicherten nach der allgemeinen Methode des Einkommensvergleichs (<ref-law>; <ref-ruling> E. 3.4 S. 348), zum Beweiswert und zur Beweiswürdigung ärztlicher Berichte und Gutachten (<ref-ruling> E. 3a S. 352 mit Hinweis), insbesondere externer Gutachten (<ref-ruling> E. 3b/bb S. 353) sowie zur Aufgabe des Arztes und der Ärztin bei der Invaliditätsbemessung (<ref-ruling> E. 4 S. 99 f. mit Hinweisen) richtig dargelegt. Korrekt sind auch die Erwägungen zu den Vergleichszeitpunkten im Falle einer Neuanmeldung (<ref-ruling> E. 3.2.3 S. 77; vgl. auch <ref-ruling> E. 5.4 S. 114). Darauf wird verwiesen.
2.2 Bei den vorinstanzlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit der versicherten Person handelt es sich grundsätzlich um Entscheidungen über eine Tatfrage (<ref-ruling> E. 3.2 S. 397 ff.). Analoges gilt auch für die Frage, ob sich eine Arbeits(un)fähigkeit in einem bestimmten Zeitraum in einem revisionsrechtlich relevanten Sinne verändert hat (vgl. Urteil I 865/06 vom 12. Oktober 2007 E. 4). Ebenso stellt die konkrete Beweiswürdigung eine Tatfrage dar. Dagegen ist die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach <ref-law> Rechtsfrage (<ref-ruling> E. 3.2 und 4 S. 397 ff.; erwähntes Ur-teil I 865/06 E. 4 mit Hinweisen), die das Bundesgericht im Rahmen der den Parteien obliegenden Begründungs- bzw. Rügepflicht (<ref-law> und <ref-law>; <ref-ruling> E. 1.4.1 und 1.4.2 S. 254) frei überprüfen kann (<ref-law>). Der Verzicht der Vorinstanz auf weitere Abklärungen oder Rückweisung der Sache an die IV-Stelle zu diesem Zwecke (antizipierte Beweiswürdigung; Urteil 9C_561/2007 vom 11. März 2008 E. 5.2.1) im Besonderen verletzt etwa dann Bundesrecht, wenn der festgestellte Sachverhalt unauflösbare Widersprüche enthält oder wenn eine entscheidwesentliche Tatfrage, wie namentlich Gesundheitszustand und Arbeitsfähigkeit einer versicherten Person, auf unvollständiger Beweisgrundlage beantwortet wird (Urteile 9C_904/2009 vom 7. Juni 2010 E. 3.1 mit Hinweisen).
3. 3.1 Die Vorinstanz prüfte im angefochtenen Entscheid, ob seit der letzten rentenablehnenden Verfügung (bestätigt mit rechtskräftigem Einspracheentscheid 4. Januar 2005) bis zur angefochtenen Verfügung vom 18. November 2008 eine wesentliche (anspruchsrelevante) Veränderung des Gesundheitszustandes eingetreten ist, nachdem die IV-Stelle dies in ihrer Beschwerdeantwort mit Verweis auf eine nachträglich eingeholte Stellungnahme des Regionalen Ärztlichen Dienstes, RAD, vom 11. März 2009, verneinte und die ursprüngliche Verfügung als falsch bezeichnete. Dabei hielt das kantonale Gericht nach Wiedergabe der medizinischen Akten fest, dass das Gutachten des Instituts Y._ vom 10. März 2008 dem Grundsatz nach voll beweiskräftig sei, nachdem es die rechtsprechungsgemäss erforderlichen Kriterien erfülle (<ref-ruling> E. 3a S. 352). Sie stellte in der Folge darauf ab, hielt aber fest, dass die im Vergleich zum MEDAS-Gutachten vom 31. August 2004 (mit 15 %) von den Gutachtern des Instituts Y._ attestierte, nunmehr höhere Arbeitsunfähigkeit von 30 % nicht nachvollziehbar sei. Entscheidend sei die Aussage der Gutachter des Instituts Y._, wonach sich der Gesundheitszustand seit 2004 nicht wesentlich verändert habe. Für den protrahierten Verlauf der Beschwerden würden invaliditätsfremde Faktoren verantwortlich gemacht, welche bei der Invaliditätsbemessung ausser Acht zu bleiben hätten. Nach Würdigung der beiden Gutachten kam sie unter Hinweis auf die Stellungnahme des RAD vom 11. März 2009 zum Schluss, dass anlässlich des Gutachtens des Instituts Y._ insgesamt lediglich ein im Wesentlichen seit 2004 gleich gebliebener Gesundheitszustand in Bezug auf dessen Auswirkungen auf die Arbeitsfähigkeit des Beschwerdeführers anders beurteilt worden sei. Da das Gutachten eine wesentliche Veränderung mit schlüssiger und überzeugender Begründung verneint habe, würden sich weitere Abklärungen erübrigen. Nachdem die im Falle einer Neuanmeldung geforderten Voraussetzungen an den Nachweis einer erheblichen Veränderung nicht erfüllt seien, sei eine Prüfung des Invaliditätsgrades nicht erforderlich.
3.2 Der Beschwerdeführer rügt unter anderem eine im Ergebnis offensichtlich unrichtige Beweiswürdigung, die zudem auf einer Verletzung bundesrechtlicher Verfahrensbestimmungen, insbesondere des Untersuchungsgrundsatzes beruhe. Er macht geltend, im MEDAS-Gutachten von 2004 sei für leidensangepasste Tätigkeiten lediglich aus psychiatrischer Sicht eine Einschränkung von 20 % festgestellt worden. Aus rheumatologischer Sicht sei für die zuletzt ausgeübte Tätigkeit und jede andere leichte Tätigkeit von einer 100%igen Arbeitsfähigkeit ausgegangen worden. Die alsdann in der Gesamtbeurteilung festgelegte Arbeitsfähigkeit von 85 % für leichte leidensangepasste Tätigkeiten beinhalte somit lediglich eine psychiatrische Einschränkung. Demgegenüber gelange das Gutachten des Instituts Y._ zu gänzlich anderen Ergebnissen. Darin werde im Vergleich zum MEDAS-Gutachten bezogen auf eine leichte Tätigkeit nicht mehr nur aus psychiatrischer Sicht Einschränkungen attestiert, sondern auch aus somatischer namentlich rheumatologischer Sicht eine Einschränkung der Arbeitsfähigkeit selbst für leichte Tätigkeiten von 20 % festgehalten.
3.3 Indem die Vorinstanz das Gutachten des Instituts Y._ vom 18. März 2008 als überzeugend und schlüssig würdigte und ihm vollen Beweiswert zuerkannte, in Bezug auf die Einschätzung der Arbeitsfähigkeit aber nicht darauf abstellte mit der Begründung, dass lediglich eine abweichende Beurteilung eines im wesentlichen unveränderten Gesundheitszustandes vorliege, ohne zumindest ergänzende Auskünfte dieser Gutachter einzuholen, ist sie im konkreten Fall ihrer Abklärungspflicht nicht genügend nachgekommen und hat den Untersuchungsgrundsatz und mithin Bundesrecht verletzt (vgl. E. 2.2 hievor). Mit dem Beschwerdeführer gilt in diesem Zusammenhang zu beachten, dass die beiden Vergleichs-Expertisen von der gleichen Begutachtungsstelle (seinerzeit noch MEDAS des Kantonsspitals X._, Universitätsklinik) und insbesondere unter der Leitung des gleichen fallverantwortlichen Oberarztes erstellt worden sind, was, wie zu Recht eingewendet wird, vermuten lässt, dass die neuerliche abweichende Einschätzung zur Arbeitsfähigkeit bewusst abgegeben wurde, zumal im Gutachten des Instituts Y._ nunmehr aus rheumatologischer Sicht eine Einschränkung festgehalten wurde und die psychiatrische Situation seit 2004 als nicht verschlechtert bezeichnet wurde. Zudem sind die von der Vorinstanz angeführten invaliditätsfremden Faktoren bereits auch im früheren Gutachten erwähnt worden. Überdies dürfte der Versicherungsmedizinischen Begutachtungsstelle wohl bekannt sein, dass diese nicht in die Arbeitsfähigkeitseinschätzung einzubeziehen sind. Die Stellungnahme des RAD vom 11. März 2009, worauf die Vorinstanz verweist, vermag nicht zu überzeugen. Entgegen dem RAD kann allein mit der Begründung, dass in der Diagnoseliste die gleichen Diagnosen aufgeführt sind wie im vormaligen MEDAS-Gutachten (mit Ausnahme der transienten Oligoarthritis der rechten Fingergelenke, was gemäss den rheumatologischen Experten ohne Einfluss auf die Arbeitsfähigkeit sei) nicht auf einen gleich gebliebenen Gesundheitszustand geschlossen werden, der etwas anders beurteilt worden ist, auch wenn nach Aussagen der Gutachter sich der Gesundheitszustand seit 2004 nicht wesentlich verändert hat. Zum einen ist die Diagnosestellung allein nicht massgebend, so kann trotz gleicher Diagnosen von einem verschlechterten Gesundheitszustand ausgegangen werden, wenn sich die Befunde ausgeprägter darstellen mit entsprechender Auswirkung auf die Leistungsfähigkeit. Zum andern kann auch schon eine relativ geringe gesundheitsbedingte Verschlechterung der Arbeitsfähigkeit anspruchserheblich und mithin revisionsrelevant sein.
3.4 Vor diesem Hintergrund ist das Bundesgericht an die vorinstanzliche Sachverhaltsfeststellung nicht gebunden. Aufgrund der unklaren medizinischen Aktenlage lässt sich allerdings die Frage, ob eine revisionsrelevante Veränderung des Gesundheitszustandes besteht, oder ob es sich tatsächlich bloss um eine andere, abweichende Beurteilung eines im Wesentlichen gleich gebliebenen Sachverhalts handelt, was keine revisionsbegründende oder im Rahmen der Revision relevante Änderung darstellen würde (<ref-ruling> S. 372 unten; SVR 2004 IV Nr. 5 S. 13 E. 2 [I 574/02]), nicht schlüssig beantworten. Auch auf das Gutachten des Instituts Y._ kann diesbezüglich nicht ohne weiteres abgestellt werden. Diese Expertise ist mit der Vorinstanz insofern unklar, als die Gutachter auf Nachfrage hin erklärten, der Gesundheitszustand habe sich seit 2004 nicht wesentlich verändert, demgegenüber aber für leichte körperliche Arbeiten eine Arbeitsfähigkeit von 70 % attestierten, während sie früher für die gleichen Tätigkeiten die Arbeitsfähigkeit auf 85 % festsetzten. Mithin ist die Sache an die IV-Stelle zurückzuweisen, damit sie die notwendigen ergänzenden medizinischen Abklärungen in die Wege leite und über den Rentenanspruch neu befinde.
4. Die Gerichtskosten werden der IV-Stelle als unterliegender Partei auferlegt (<ref-law>). Diese hat dem obsiegenden Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird in dem Sinne gutgeheissen, dass der Entscheid des Versicherungsgerichts des Kantons Solothurn vom 14. Januar 2010 und die Verfügung der IV-Stelle des Kantons Solothurn vom 18. November 2008 aufgehoben werden und die Sache an die IV-Stelle zurückgewiesen wird, damit diese nach erfolgter Abklärung im Sinne der Erwägungen über das Rentengesuch neu verfüge.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Versicherungsgericht des Kantons Solothurn zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 3. November 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Weber Peter