Faits: A. Par décision du 17 décembre 2008, l'Office cantonal de l'assurance-invalidité du canton de Genève a rejeté la demande de prestations de l'assurance-invalidité présentée par P._, au motif qu'elle n'était pas invalide. B. L'intéressée a recouru contre cette décision par acte du 2 février 2009 adressé au Tribunal cantonal genevois des assurances sociales et déposé le même jour au poste de douane X._ (canton Y._). Le carton contenant cet acte comportait la mention: "Déposé à la douane suisse pour transmission à l'autorité compétente". L'acte fut remis le jour suivant à la poste. Après avoir entendu les parties et les avoir invitées à s'exprimer sur la recevabilité du recours, le Tribunal cantonal des assurances sociales de la République et canton de Genève a déclaré le recours du 2 février 2009 irrecevable, faute d'avoir été déposé "en temps utile devant une autorité utile". C. P._ interjette un recours en matière de droit public contre le jugement cantonal dont elle demande l'annulation, sous suite de dépens. Elle conclut à ce que son recours du 2 février 2009 soit déclaré recevable et la cause renvoyée au Tribunal cantonal genevois des assurances sociales. Elle demande en outre à ce que la procédure soit déclarée gratuite. Invités à se déterminer, l'Office cantonal de l'assurance-invalidité du canton de Genève conclut au rejet du recours tandis que l'Office fédéral des assurances sociales a renoncé à se prononcer.