Faits:
A. A._ a été victime d'harcèlement entre juin 2000 et début septembre 2002.
Par jugement du 2 février 2004, le Tribunal de police de la République et canton de Genève (ci-après: le Tribunal de police) a reconnu le prévenu coupable de lésions corporelles simples et d'utilisation abusive d'une installation de télécommunication. Il l'a condamné à une peine d'emprisonnement ainsi qu'au versement, en faveur de la victime, d'un montant global de 6'301 fr. composé de la manière suivante: 2'310 fr. à titre de réparation du dommage matériel, 2'500 fr. à titre d'indemnité pour tort moral et 1'500 fr. à titre de participation aux honoraires d'avocat.
B. Le 7 février 2004, A._ a saisi l'Instance d'indemnisation de la loi fédérale sur l'aide aux victimes d'infractions de la République et canton de Genève (ci-après: l'Instance LAVI) d'une requête en indemnisation pour le dommage matériel et le tort moral subis. Elle a conclu à ce que lui soient versés 2'500 fr. à titre de réparation du tort moral, 22'007 fr. 25 à titre de frais d'avocat et 2'503 fr. à titre de frais de justice.
Le 24 mars 2006, A._ a informé l'Instance LAVI que le condamné lui avait versé le montant de 6'301 fr. fixé par le Tribunal de police. Elle a alors renoncé à ses conclusions visant au paiement d'une indemnité pour tort moral ainsi qu'au remboursement des frais de justice. Elle a néanmoins persisté à réclamer l'indemnisation de ses frais d'avocats, à savoir 22'007 fr. 25 et 3'001 fr. 70, selon les notes d'honoraires des 7 février 2004 et 24 mars 2006, soit au total 25'008 fr. 95, sous déduction des 1'500 fr. payés par le condamné.
C. Par ordonnance du 11 juillet 2006, l'Instance LAVI a rejeté la requête de A._, au motif que l'agresseur s'était acquitté des dépens fixés par le Tribunal de police.
Par arrêt du 16 janvier 2007, le Tribunal administratif a annulé cette ordonnance. Appliquant le tarif de l'assistance juridique, il a notamment alloué à A._, une indemnisation LAVI de 14'514 fr. 55 au titre des frais d'avocat encourus dans la procédure pénale, sous déduction des 1'500 fr. déjà reçus.
D. Agissant par la voie du recours en matière de droit public, le Département fédéral de justice et police (DFJP) demande au Tribunal fédéral d'annuler l'arrêt rendu par le Tribunal administratif le 16 janvier 2007 et de renvoyer la cause à cette autorité pour nouvelle décision dans le sens des considérants. Il se plaint d'une violation de la loi fédérale sur l'aide aux victimes d'infractions (LAVI).
Le Tribunal administratif s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. A._ conclut au rejet du recours.

Le Tribunal fédéral considère en droit:
1. La décision attaquée ayant été rendue après le 1er janvier 2007, la loi sur le Tribunal fédéral du 17 juin 2005 (LTF) est applicable à la présente procédure de recours (<ref-law>).
2. L'arrêt entrepris peut faire l'objet d'un recours en matière de droit public selon les <ref-law>. Le Département fédéral de justice et police, compétent en la matière, a qualité pour recourir (<ref-law>). Les autres conditions de recevabilité énoncées aux <ref-law> étant satisfaites, il y a lieu d'entrer en matière.
3. Le DFJP soutient qu'en jugeant que l'intimée avait droit à une indemnisation en vertu des art. 11 ss de la loi fédérale du 4 octobre 1991 sur l'aide aux victimes d'infractions (LAVI; RS 312.5), alors que l'auteur de l'infraction avait versé l'intégralité des sommes qu'il devait selon le jugement du Tribunal de police, le Tribunal administratif a violé les règles applicables en matière de LAVI.
Il s'agit dès lors uniquement d'examiner en l'espèce si, lorsque les dépens alloués à la victime par le juge pénal incluent la couverture des frais d'avocat, cette dernière est encore légitimée à réclamer une indemnisation LAVI pour les honoraires d'avocat qui vont au-delà de cette somme.
4. En matière de LAVI, la notion de dommage correspond en principe à celle du droit de la responsabilité civile (<ref-ruling> consid. 2.1 p. 125; FF 1990 II 909, 939; Peter Gomm/Dominik Zehntner, Kommentar zum Opferhilfegesetz, Berne 2005, p. 245; Eva Weishaupt, Finanzielle Ansprüche nach Opferhilfegesetz in SJZ 98 322, 327).
4.1 En droit de la responsabilité civile, les frais engagés par la victime pour la consultation d'un avocat avant l'ouverture du procès civil, lorsque cette démarche était nécessaire et adéquate, peuvent constituer un élément du dommage, pour autant que ces frais n'aient pas été inclus dans les dépens. Il en va de même pour les frais engagés dans une autre procédure, comme une procédure pénale par exemple. Si cette procédure permet d'obtenir des dépens, même tarifés, il n'est alors plus possible de faire valoir une prétention en remboursement des frais de défense par une action ultérieure en responsabilité civile (arrêt 4C.51/2000 du 7 août 2000 consid. 2 publié in SJ 2001 I 153; <ref-ruling> consid. 5 p. 106; <ref-ruling> consid. 3a p. 356).
Cette réglementation repose sur des considérations pratiques et la recherche d'un équilibre entre des intérêts divergents; cet équilibre se trouverait compromis si la décision sur les dépens ne liquidait pas les prétentions des parties et laissait la porte ouverte à une action civile ultérieure (ATF <ref-ruling> consid. 3a p. 357).
4.2 Dans le canton de Genève, l'art. 97 al. 1 du code de procédure pénale (CPP/GE) met à la charge du condamné les dépens de la partie civile devant les juridictions de jugement. Ces dépens sont calculés conformément au tarif établi par le Conseil d'Etat (<ref-law>/GE). Selon l'art. 12 al. 1 du règlement fixant le tarif des frais et dépens en matière pénale (ci-après: le règlement), les dépens dus par le condamné comprennent les débours ainsi qu'une participation aux honoraires d'avocat allant en particulier de 50 à 1'000 fr. devant le Tribunal de police (let. b). Aux termes de l'alinéa 2 de cette même disposition, l'autorité de jugement peut accorder, à titre exceptionnel, une participation d'un montant supérieur en raison de circonstances particulières, notamment les difficultés du procès, la situation financière des parties, la durée de la procédure ou encore l'ampleur des débats.
4.3 Le Tribunal fédéral a jugé que, en droit cantonal genevois, l'usage de l'expression "participation aux honoraires d'avocat" ne signifiait pas que l'indemnité pour les dépens ne correspondait qu'à une quotité déterminée des honoraires totaux de l'avocat. Les dépens permettaient le dédommagement de tous les frais d'avocat rendus nécessaires par le procès (arrêt P.367/73 du 29 mars 1973 consid. 4a publié in SJ 1973 337; arrêt P.287/1981 du 17 juillet 1981 consid. 3a publié in SJ 1982 289; arrêt 4C.80/1995 du 28 août 1995 consid. 2 publié in SJ 1996 299; arrêt 4C.51/2000 précité, consid. 3). La partie civile ne dispose donc pas d'une prétention en dommages-intérêts pour la part non couverte par les dépens (arrêt 4C.51/2000 précité, consid. 3).
4.4 Selon l'art. 6 du règlement, les parties, ou s'il est condamné, le plaignant, peuvent faire opposition à la taxation de l'état de frais de l'Etat ou à celle des dépens d'une partie auprès de la Cour de justice qui statue en dernier ressort.
5. 5.1 Le législateur n'a certes pas choisi de reprendre en tous points, dans le système des <ref-law>, le régime du droit de la responsabilité civile. Des solutions spécifiques sont donc possibles (<ref-ruling> consid. 2.2 p. 125 s.).
En matière de détermination du dommage, des différences ne se justifient cependant qu'exceptionnellement (cf. p. ex. <ref-law>). En effet, la LAVI n'a pas à couvrir des dommages qui vont au-delà de la responsabilité civile de l'auteur. Si une des conditions des <ref-law> fait défaut, une indemnisation LAVI n'entre dès lors pas en considération (Eva Weishaupt, op. cit., p. 325).
Le Tribunal fédéral a d'ailleurs lui-même souligné que la victime devait être admise à faire valoir, dans le cadre des <ref-law>, des prétentions pour les différents postes du dommage qui entreraient en considération selon l'<ref-law> (<ref-ruling> consid. 2.4.4 p. 129). Il n'y a dès lors pas de raison d'admettre que la victime LAVI puisse être indemnisée pour un dommage dont elle ne pourrait pas obtenir réparation selon les règles du droit de la responsabilité civile. De plus, la victime a l'obligation de limiter le dommage qu'elle subit dans toute la mesure du possible (arrêt 1A.169/2001 du 7 février 2002 consid. 3.2).
5.2 Le Tribunal fédéral a, il est vrai, admis que les frais d'avocat pouvaient constituer un poste du dommage indemnisé sur la base des <ref-law> (<ref-ruling>). Il n'a cependant fait qu'admettre le principe d'une telle indemnisation (cf. <ref-ruling> consid. 2.4.4 dernier paragraphe p. 129). En effet, seules étaient alors litigieuses les questions concernant les rapports de subsidiarité entre l'assistance judiciaire, l'<ref-law> et les <ref-law> ainsi que le tarif à appliquer aux honoraires d'avocat réclamés. Le Tribunal fédéral n'a donc pas été amené à examiner dans ce cadre la question particulière du sort des dépens alloués à la victime par le juge pénal.
On ne saurait dès lors déduire de la jurisprudence un droit automatique à une indemnisation des frais d'avocat fondée sur les <ref-law>, même si des dépens ont été accordés à la victime dans le cadre du procès pénal.
5.3 La victime diligente, en cas de refus de l'assistance judiciaire, doit en principe immédiatement s'adresser au centre de consultation pour requérir l'aide juridique, afin que la question de l'application de l'<ref-law> soit résolue d'emblée. Cela permet à l'autorité d'exercer un contrôle sur les frais d'avocat et de procédure engagés. Le Tribunal fédéral a certes concédé que si la victime omettait d'emprunter la voie prévue par l'<ref-law>, son droit au remboursement des frais d'avocat dans le cadre des <ref-law> ne se périmait pas. Il a cependant précisé que la victime prenait ainsi néanmoins le risque d'engager des frais dont elle n'obtiendrait peut-être pas le remboursement (<ref-ruling> consid. 2.4.1 p. 127 s.).
5.4 La pratique genevoise qui consiste à renvoyer les victimes LAVI à s'adresser à l'Instance LAVI pour obtenir le remboursement du montant qui dépasse les dépens fixés dans le cadre de la procédure pénale ne se concilie pas avec les principes de la LAVI (cf. consid. 5.2). Elle est également contraire à l'<ref-law>/GE qui prévoit que les dépens de la partie civile sont à la charge du condamné.
Les victimes LAVI devraient obtenir dans le cadre de la procédure pénale la condamnation de l'auteur au paiement de l'intégralité des honoraires d'avocat, sous réserve de leur proportionnalité (cf. consid. 6.3).
En l'espèce, la victime n'a pas requis l'assistance judiciaire ordinaire, elle n'a pas non plus sollicité l'aide juridique du Centre de consultation LAVI et elle n'a pas contesté le montant des dépens qui lui ont été alloués par le juge pénal. Ce comportement, ajouté à la pratique genevoise en matière de dépens, a pour effet que, selon la jurisprudence rappelée plus haut (consid. 4.1), l'auteur de l'infraction ne peut être recherché pour le remboursement des frais de la victime, ce qui est contraire au principe de subsidiarité qui est à la base du système LAVI (<ref-law> et 4 nLAVI). Dans ces conditions, la victime doit se laisser opposer un refus d'indemnisation.
6. Ces considérants précisent l'<ref-ruling> qui a pu créer une certaine confusion. En outre, la pratique genevoise a pu induire en erreur l'intimée. Il se justifie dès lors à titre exceptionnel, à la suite de cette précision de la jurisprudence, de renvoyer la cause au Tribunal administratif pour qu'il statue sur la demande d'indemnisation selon la portée qui pouvait être donnée à l'arrêt précité.
6.1 Le Tribunal administratif devra examiner si les conditions de limites de revenu de la victime (<ref-law>) pour prétendre à une indemnisation sont réalisées, puisque cette question a été négligée jusqu'ici.
6.2 Par ailleurs, il sera rappelé que l'indemnisation ne pourra pas excéder le montant qui aurait été alloué en application du tarif de l'assistance judiciaire en vertu de la jurisprudence encore appliquée à titre exceptionnel dans la présente cause (<ref-ruling> consid. 2.5.2 p. 131).
6.3 Enfin, seule l'activité strictement nécessaire à la défense des droits de la victime peut être indemnisée, à l'exclusion de toutes démarches inutiles ou superflues. Il n'appartient pas à l'Etat de prendre en charge des frais qui ne seraient pas dans un rapport raisonnable avec les prétentions que la victime peut faire valoir (arrêt 1A.169/2001 précité consid. 3.2). Dans la mesure où cette question n'a pas davantage été traitée, le Tribunal administratif devra donc examiner l'activité déployée par l'avocat et vérifier s'il n'y a pas lieu de réduire l'indemnité à ce titre également.
7. Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé, l'affaire étant renvoyée au Tribunal administratif pour nouvelle décision.
Il n'y a pas lieu de percevoir un émolument judiciaire, la procédure de recours étant gratuite en la matière (<ref-ruling> consid. 3 p. 132; <ref-ruling> consid. 4b p. 219). Ni l'intimée, qui succombe, ni les collectivités publiques parties à la procédure, n'ont droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée au Tribunal administratif pour nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué en copie au Département fédéral de justice et police (Office fédéral de la justice), au mandataire de l'intimée, à l'instance d'indemnisation LAVI et au Tribunal administratif de la République et canton de Genève.
Lausanne, le 12 juillet 2007
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le président: La greffière: