Faits:
A. A.a Par décision du 23 avril 2003, reposant sur un prononcé de l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: l'OAI-NE) du 23 décembre 2002, l'Office de l'assurance-invalidité pour les assurés résidant à l'étranger (ci-après: l'OAIE) a octroyé à S._ une rente entière d'invalidité du 1er mars 2000 au 31 mai 2001. L'autorité expliquait qu'à réception de l'attestation des périodes d'assurance françaises, elle examinerait s'il y avait lieu de recalculer la rente, qu'une formule à remplir était jointe à la décision afin de permettre le paiement sur un compte bancaire et qu'elle avait placé la somme due à titre rétroactif sur un compte d'attente en prévision d'une éventuelle surindemnisation avec la Caisse nationale suisse d'assurance en cas d'accidents (CNA).
Après avoir recalculé la rente en tenant compte des périodes d'assurance accomplies en France, l'OAIE a, par décision du 4 août 2004, remplacé la décision du 23 avril 2003 en octroyant des prestations d'un montant supérieur pour la période concernée par le droit à la rente et versé le différentiel sur le compte d'attente.
A.b L'avocat de S._, Me Bruno Kaufmann, s'est opposé à la décision du 4 août 2004 par acte du 8 septembre 2004. Il a fait valoir que la décision précitée ne mentionnait aucun motif pour lequel le droit à la rente était limité dans le temps et a requis l'octroi d'une demi-rente pour une durée illimitée. Il a également reproché à l'autorité le «remboursement» des rentes rétroactives à la CNA à hauteur de 17'415 fr. Il annonçait par ailleurs un complément à son écriture, lequel n'est jamais parvenu. En revanche, il s'est enquis de l'avancement de la procédure par courrier du 15 février 2005 auquel l'autorité a répondu le 16 février 2005, réponse que le représentant de l'assuré a prétendu ne jamais avoir reçue (cf. lettre de Me Kaufmann du 15 novembre 2005).
Par décision du 11 décembre 2006, l'OAIE a rejeté l'opposition de S._.
B. Par arrêt du 24 juin 2009, le Tribunal administratif fédéral a rejeté le recours formé par S._ contre la décision sur opposition du 11 décembre 2006. En substance, les premiers juges ont retenu que l'OAIE aurait dû déclarer irrecevable l'opposition de l'assuré contre sa décision du 4 août 2004 car ce dernier soulevait des griefs ayant trait à la décision du 23 avril 2003, laquelle était entrée en force. L'avocat du recourant ayant soulevé l'irrégularité de la notification de la décision du 23 avril 2003, affirmant ne jamais l'avoir reçue, le tribunal de première instance a considéré qu'un faisceau d'indices montrait que dite décision avait été envoyée au mandataire ou, à tout le moins, que ce dernier en avait eu connaissance à une date indéfinie mais dont le délai pour recourir était très vraisemblablement échu.
C. S._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation en concluant, sous suite de frais et dépens, au renvoi de la cause au Tribunal administratif fédéral afin qu'il entre en matière sur le fond du litige.
L'OAIE conclut au rejet du recours et à la confirmation du jugement attaqué.

Considérant en droit:
1. Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être limité par les arguments de la partie recourante ou par la motivation de l'autorité précédente. Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'<ref-law>, et ne peut aller au-delà des conclusions des parties (<ref-law>). Il fonde son raisonnement sur les faits retenus par la juridiction de première instance (<ref-law>) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). La partie recourante qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> sont réalisées sinon un état de fait divergent ne peut être pris en considération. Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2. 2.1 Les premiers juges ont retenu que le sort de la demande de prestations déposée par le recourant avait été réglé par décision de l'OAIE du 23 avril 2003, laquelle avait été envoyée par courrier recommandé à l'avocat du recourant, avec copie à l'OAI-NE, au recourant, à la CNA ainsi qu'au centre de liaisons européennes et internationales de la sécurité sociale à Paris. Cette décision reconnaissait au recourant un droit à une rente entière d'invalidité d'un montant de 1'370 fr. à partir du 1er mars jusqu'au 31 décembre 2000 et de 1'405 fr. du 1er janvier au 31 mai 2001, assortie de deux rentes complémentaires pour ses filles. Le calcul à la base des montants alloués prenait en compte une durée de cotisations de 19 ans, un revenu annuel moyen déterminant de 74'160 fr. et l'échelle de rente 30 pour 19 années entières d'assurance sur 28 années de sa classe d'âge. Les moyens de droit figuraient sur la dernière page de la décision à laquelle était annexée la motivation. Le recourant ne s'était pas opposé à cette décision qui était par conséquent entrée en force 30 jours après sa notification. Dans sa décision du 4 août 2004 remplaçant celle du 23 avril 2003, l'OAIE avait tenu compte des périodes françaises d'assurance, appliqué l'échelle de rente 44 pour 28 années entières d'assurance et adapté le montant des rentes en conséquence. Le différentiel de 17'415 fr. devait être versé sur le compte d'attente. La décision était assortie des moyens de droit.
2.2 Selon les premiers juges, seule la partie de la décision du 23 avril 2003 concernant le calcul de la rente avait été remplacée par la décision du 4 août 2004. Par conséquent, les autres aspects de la décision du 23 avril 2003, (à savoir notamment le droit à la rente comme tel et la durée de ce droit) avaient acquis l'autorité de la chose jugée, faute pour le recourant d'avoir attaqué cette décision dans le délai de recours.
2.3 Le recourant ayant prétendu ne jamais avoir reçu la décision du 23 avril 2003, les premiers juges sont arrivés à la conclusion qu'un faisceau d'indices montrait que cette décision avait été envoyée au mandataire ou, à tout le moins, que ce dernier en avait eu ou aurait dû en avoir connaissance à une date indéfinie mais dont le délai pour recourir était très vraisemblablement échu. Les indices retenus par le Tribunal administratif fédéral sont les suivants:
- une copie de la décision du 23 avril 2003 figurait non seulement dans le dossier de l'OAIE mais également au dossier de l'OAI-NE et de la CNA, ce qui prouvait qu'elle avait bien été envoyée;
- selon les termes mêmes de la décision, une formule à remplir était jointe à celle-ci afin de permettre le paiement sur un compte bancaire ou postal. Or, selon le dossier constitué par l'OAIE, ce formulaire avait été rempli par le recourant le 7 mai 2003 et réceptionné par l'autorité le 13 mai 2003;
- par décision du 14 août 2003, la CNA avait informé l'avocat du recourant, par courrier recommandé, de la compensation à hauteur de 11'661 fr. 20 de sa créance en restitution avec les arrérages de l'assurance-invalidité. Or, ce calcul n'avait été possible qu'après décision de l'OAIE comme le laissait clairement apparaître le décompte de surindemnisation qui était joint;
- le 20 août 2003, la Caisse suisse de compensation avait transmis au recourant un décompte libérant - après compensation avec la CNA - un rétroactif de 25'643 fr. 80 en sa faveur «selon la décision du 23 avril 2003».
3. Dans un premier moyen, le recourant relève que la motivation annexée à la décision du 23 avril 2003 ne pouvait pas entrer en force de chose jugée et que l'OAIE ne voulait pas définitivement régler le droit à la rente du recourant dans sa décision du 23 avril 2003.
Dans un arrêt publié aux <ref-ruling>, le Tribunal fédéral des assurances avait considéré qu'en cas de remplacement d'une rente en cours par une rente d'un autre genre (p. ex. lorsqu'une rente d'invalidité est remplacée par une rente de vieillesse), la force formelle attachée à l'ancienne décision de rente ne liait pas le juge appelé à se prononcer sur la nouvelle décision dès lors qu'on se trouvait dans un nouveau cas d'assurance. Ainsi que l'ont relevé à juste titre les premiers juges, le cas d'espèce est différent puisque la décision du 4 août 2004 n'avait pas pour objet l'attribution d'un nouveau type de rente mais seulement une modification des bases de calcul de la (même) rente ayant fait l'objet de la décision du 23 avril 2003. Par conséquent, tous les aspects du droit à la rente ne concernant pas à proprement parler ses bases de calcul étaient entrés en force de chose jugée au moment où l'avait été la décision du 23 avril 2003. Comme l'ont démontré les premiers juges, le cas présent se distingue également de l'affaire jugée par arrêt I 11/04, du 5 août 2004.
4. 4.1 Dans un second moyen, le recourant conteste la motivation des premiers juges selon laquelle son avocat aurait eu ou dû avoir connaissance de la décision du 23 avril 2003. Selon lui, la preuve de la notification d'une décision administrative par l'autorité l'ayant rendue doit être établie de manière absolue, le degré de la vraisemblance prépondérante retenu par les premiers juges n'étant pas suffisant.
4.2 Selon la jurisprudence, la notification d'un acte ou d'une décision n'est soumise à la règle de la preuve stricte qu'en cas de procès pendant et non pas déjà au stade de l'administration de masse. La règle du degré de vraisemblance prépondérante, applicable généralement dans le domaine du droit des assurances sociales, est donc suffisante en ce qui concerne la preuve de faits déterminants pour la notification d'une décision ou d'une décision sur opposition de l'administration (<ref-ruling> consid. 3b p. 6, 119 V 7 consid. 3c/aa p. 9; arrêt du Tribunal fédéral 9C_639/2007 du 25 février 2008).
4.3 En l'espèce, les premiers juges ont retenu que sur le vu de l'ensemble des éléments ressortant du dossier - en particulier les quatre indices énumérés ci-dessus -, il y avait lieu de considérer comme établi au degré de la vraisemblance prépondérante que l'avocat du recourant avait bel et bien eu connaissance de la décision du 23 avril 2003. Si le premier indice retenu par les premiers juges n'est pas particulièrement pertinent, dès lors que selon la jurisprudence, la seule présence de la copie d'une lettre n'autorise pas à conclure avec un degré de vraisemblance prépondérante que cette lettre a été effectivement envoyée par son expéditeur et qu'elle a été reçue par le destinataire (<ref-ruling> consid. 1), le deuxième indice est quant à lui déterminant. En effet, si le recourant a dûment rempli puis renvoyé à la Caisse suisse de compensation le formulaire concernant ses données bancaires annexé à la décision du 23 avril 2003, il devait nécessairement avoir reçu cette décision avec ses annexes (donc également la motivation de la décision en dépit du fait qu'il prétend le contraire). Ce formulaire, complété par le recourant le 7 mai 2003, a été réceptionné par l'administration le 13 mai 2003, de sorte que l'on ne saurait se fonder sur les déclarations du recourant ou de son mandataire prétendant n'avoir eu connaissance de la décision du 23 avril 2003 que récemment. Enfin, on relèvera que le troisième indice retenu par les premiers juges est lui aussi très pertinent, d'autant plus que le recourant n'a jamais contesté avoir reçu la décision de la CNA du 14 août 2003 (et du décompte annexé) par laquelle elle l'informait d'une compensation d'un montant de 11'661 fr. 20 de sa créance en restitution avec les arrérages de l'assurance-invalidité. Compte tenu de ce qui précède, c'est donc à bon droit que le Tribunal administratif fédéral a tenu pour établi que l'avocat du recourant avait eu connaissance de la décision du 23 avril 2003 ou aurait dû en avoir connaissance s'il avait fait preuve de l'attention que l'on est en droit d'attendre d'un mandataire professionnel. Quant à la date à laquelle le recourant, respectivement son mandataire, est réputé avoir pris connaissance de la décision du 23 avril 2003, elle n'a en revanche pas été établie par la juridiction de première instance. Toutefois, dans la mesure où les indices sur lesquels se sont fondés les premiers juges pour établir la preuve de la notification reposent sur des faits datant de l'année 2003, on peut sans autre admettre que l'opposition du recourant déposée le 8 septembre 2004 était tardive et par conséquent irrecevable. Partant, le recours est mal fondé.
5. Le recourant, qui succombe, supportera les frais de la procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
3. La présente ordonnance est communiquée aux parties, au Tribunal administratif fédéral, Cour III, et à l'Office fédéral des assurances sociales.
Lucerne, le 26 février 2010
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Fretz