Faits:
A. C._ est née en 1988 en Algérie de l'union de A.X._, né en 1958 et de B.X._, née en 1963.
Les trois membres de cette famille sont entrés en Suisse illégalement en 1989. Dès le début des années 1990 et jusqu'au mois de mars 2000, les époux X._ ont déposé de multiples requêtes en matière d'asile, qu'il s'agisse de demandes de reconsidération ou de réexamen, ainsi que plusieurs recours tendant à repousser leur renvoi de Suisse qui leur a été signifié pour la première fois avec effet au 11 janvier 1995. Les multiples démarches procédurales liées à cet aspect du dossier seront exposées ci-après dans la partie "En droit" en tant que nécessaire.
Le 25 novembre 2008, agissant par l'intermédiaire d'un avocat, C.X._ et son fiancé, ressortissant suisse, ont informé le Service de la population du canton de Vaud qu'ils entamaient des démarches en vue de régulariser la situation illégale de celle-ci de manière à permettre le mariage. Le Service de la population a requis le 17 février 2009 la production de diverses pièces et demandé aux fiancés de fournir des explications. Informé à cette occasion de la présence illégale de C.X._, le Service de la population a requis la Police cantonale, le 1er avril 2009, d'effectuer une enquête relative à la situation de l'intéressée et à celle de ses parents. Cette enquête a mis en lumière que la famille X._ occupait depuis 2001 un logement à D._ et que A.X._ et son épouse avaient travaillé depuis 2001, tous deux à temps complet, respectivement en qualité d'homme à tout faire et d'employée de maison au service d'une personne domiciliée à E._.
B. Le 15 juillet 2009, les membres de la famille X._ ont déposé un rapport d'arrivée auprès de la commune de D._ et ont indiqué à cette occasion une date d'entrée en Suisse remontant au 30 août 1998 ainsi qu'une arrivée dans le canton de Vaud au mois de février 2000. Ils ont sollicité l'octroi d'une autorisation de séjour en application des art. 30 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) et 31 de l'ordonnance du 24 octobre 2007 relative à
l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201).
Par décision du 10 novembre 2009, le Service de la population a informé A.X._, B.X._ et C.X._ qu'il ne pouvait donner une suite favorable à leur demande d'autorisation de séjour et leur a opposé à cette occasion le principe d'exclusivité de la procédure d'asile. Il leur a fait savoir qu'ils étaient tenus de retourner dans leur canton d'attribution, à savoir le canton de Fribourg, seul compétent pour l'exécution de leur renvoi vers l'Algérie.
C. Le 16 décembre 2009, les trois membres de la famille X._ ont saisi la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) d'un recours dirigé contre le refus du Service de la population. Ils ont conclu à l'annulation de cette décision, ainsi qu'à l'octroi d'une autorisation de séjour en vertu des art. 8 CEDH et 30 al. 1 LEtr, subsidiairement à ce que l'exécution du renvoi soit considérée comme illicite.
Par arrêt du 4 mai 2010, le Tribunal cantonal a admis le recours de C.X._ et rejeté celui de ses parents, dans la mesure de sa recevabilité, en se fondant pour l'essentiel sur le principe d'exclusivité de l'art. 14 de la loi fédérale du 26 juin 1998 sur l'asile (LAsi; RS 142.31). A cette occasion, le Tribunal cantonal a analysé en détail le parcours des membres de la famille X._ en Suisse.
D. Par écriture parvenue au Tribunal fédéral le 7 juin 2010, A.X._ et B.X._ ont interjeté un recours en matière de droit public à l'encontre de l'arrêt du Tribunal cantonal du 4 mai 2010. Ils ont conclu principalement à l'octroi d'une autorisation de séjour fondée sur les art. 8 CEDH et 30 al. 1 let. b LEtr, ainsi que, subsidiairement, au constat de l'illicéité de l'exécution du renvoi. Ils ont en outre déposé une requête d'effet suspensif, qui a été acceptée par ordonnance présidentielle du 15 juin 2010.
Se déterminant sur le recours, le Tribunal cantonal et le Service de la population ont renoncé à prendre des conclusions spécifiques, alors que l'Office fédéral des migrations a conclu à son rejet.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 444; <ref-ruling> cons. 1 p. 521 et les arrêts cités).
1.1 Le 10 novembre 2009, le Service de la population a avisé les trois membres de la famille X._ du fait qu'il ne pouvait "malheureusement pas donner suite à leur demande d'autorisation de séjour, au regard du principe d'exclusivité de la procédure d'asile", dans la mesure où ils devaient auparavant avoir quitté la Suisse pour pouvoir introduire une requête d'autorisation de séjour. La référence à l'<ref-law> ne laisse pas planer de doute sur le fait qu'il s'agissait d'une décision d'irrecevabilité, même si cette dernière n'a pas formellement été libellée comme telle. La présente procédure ne peut dès lors porter sur l'octroi de l'autorisation de séjour en tant que telle, mais uniquement sur l'existence d'un éventuel droit des recourants à obtenir celle-ci au titre du respect de la vie privée garanti par l'art. 8 CEDH, ce qui leur permettrait d'en faire la demande sans devoir quitter la Suisse comme le prévoit l'<ref-law> (cf. arrêts 2C_733/2008 du 12 mars 2009 consid. 2; 2C_551/2008 du 17 novembre 2008 consid. 3.2).
Du moment qu'il ne contient que des conclusions au fond, à savoir tendant à l'octroi d'une autorisation de séjour que le Tribunal fédéral n'est pas apte à accorder dans de telles circonstances, le recours est donc irrecevable.
1.2 De plus, s'agissant du grief de violation de l'art. 8 CEDH, le Tribunal de céans a déjà eu l'occasion de relever que cette disposition conventionnelle ne confère pas un droit à attendre en Suisse l'issue de la procédure d'autorisation de séjour (arrêts 2C_483/2009 du 18 septembre 2009 consid. 4.2; 2C_11/2007 du 21 juin 2007 consid. 2.3.3).
1.3 En outre, aux termes de l'art. 83 let. c ch. 4 LTF, les décisions relatives au renvoi ne peuvent faire l'objet d'un recours au Tribunal fédéral. La conclusion subsidiaire des recourants est donc irrecevable.
1.4 Comme indiqué ci-dessus, dans le contexte de l'<ref-law>, une demande d'autorisation de séjour fondée uniquement sur l'art. 8 CEDH ne peut être introduite qu'après le renvoi de l'étranger concerné. Une exception au principe de l'exclusivité de la procédure d'asile n'est admise que si le droit à l'autorisation de séjour requise est manifeste (arrêts 2C_733/2008 précité consid. 5.1; 2A.673/2006 du 18 décembre 2006 consid. 3.3). Or, en se fondant exclusivement sur le droit à la protection de la vie privée garanti par l'art. 8 CEDH et pouvant consacrer un droit exceptionnel à une autorisation de police des étrangers, les recourants ne remplissent manifestement pas cette condition. En particulier, l'invocation de l'arrêt 2C_266/2009 du 2 février 2010 ne leur est d'aucun secours. En effet, dans dite cause, le recourant s'était de tout temps conformé à l'ordre juridique suisse, en particulier aux normes du droit des étrangers. Or, il en va tout autrement en l'espèce où, après avoir séjourné illégalement en Suisse depuis 1989 et à la suite du rejet de leur demande d'asile, les recourants ont fait l'objet d'une interdiction d'entrée en Suisse jusqu'en 1995. Ils sont malgré tout demeurés dans le pays et, en 1994, une nouvelle interdiction d'entrée en Suisse leur a été notifiée avec effet jusqu'en 1997. Cela n'a pas empêché A.X._ d'être refoulé à la frontière le 5 février 1998, alors qu'il tentait de pénétrer illégalement sur le territoire national. Les membres de la famille sont à nouveau revenus en Suisse illégalement en 1998 et ont été interpellés par la Police municipale de Lausanne le 1er février 1999. Ils ont alors déposé une nouvelle demande d'asile, qui a été rejetée le 21 avril 1999, ce qui a débouché sur un nouvel ordre de renvoi, un délai leur ayant été fixé au 15 juin 1999 pour quitter la Suisse. A la suite du rejet de leur recours, un nouveau délai échéant le 31 juillet 1999 leur a été imparti pour ce faire. Une demande de prolongation de délai a été rejetée le 13 août 1999 et une demande de réexamen a connu le même sort le 28 octobre 1999. Une nouvelle demande de réexamen a été rejetée le 27 janvier 2000. Le 14 février 2000, les membres de la famille X._ ont demandé à pouvoir demeurer en Suisse jusqu'à la fin de l'année scolaire, ce qui a été refusé le 22 février 2000. Ils ne se sont pas présentés à l'aéroport pour le vol de retour prévu le 9 mars 2000. Après - semble-t-il - un court séjour en France, ils sont revenus en Suisse où C.X._ a été scolarisée dans le canton de Vaud dès le 13 mars 2000. Informée de la présence illégale de cette dernière à l'occasion d'une requête de régularisation déposée en vue de son mariage, la Police cantonale vaudoise a établi que la famille occupait depuis 2001 un logement à D._, en l'absence de toute autorisation de séjour. C'est dire que le comportement administratif de la famille X._ est loin d'être exempt de reproches, à la différence de ce qui prévalait dans l'arrêt qu'elle invoque. Au contraire, c'est exclusivement en abusant de manière évidente des moyens de droit à sa disposition, puis en demeurant en Suisse sans droit, qu'elle s'est mise dans la situation difficile qui est la sienne aujourd'hui. Il est à cet égard certain que le respect de l'injonction de quitter la Suisse, en 1995, aurait mis les membres de la famille X._ à l'abri de l'obligation de partir au terme de vingt ans de vie dans cet Etat, étant ainsi posé qu'ils sont les seuls artisans de cette situation. Ils ne sauraient donc déduire quelque droit que ce soit de cet état de fait, de sorte que l'invocation de l'art. 8 CEDH ne leur est d'aucun secours. Leur bonne intégration en Suisse, qui n'est pas contestée, ne permet pas une autre conclusion. Cela fait que, même recevable, leur requête aurait dû être rejetée.
1.5 Les recourants se prévalent enfin de l'art. 30 al. 1 let. b LEtr régissant également le cas de rigueur. Outre qu'il n'existe pas de droit à une dérogation aux conditions d'admission selon l'art. 30 LEtr, de sorte que le recours en matière de droit public est exclu à cet égard (art. 83 let. c ch. 5 LTF), l'<ref-law> fait aussi obstacle à l'invocation de l'art. 30 al. 1 let. b LEtr au regard de l'exclusivité de la procédure d'asile, comme déjà exposé ci-dessus. Le grief est donc irrecevable.
2. Vu ce qui précède, le recours doit être déclaré irrecevable.
Succombant, les recourants doivent supporter un émolument judiciaire, solidairement entre eux (cf. art. 66 al. 1 et 5 LTF) et n'ont pas droit à des dépens (cf. <ref-law> a contrario).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Un émolument judiciaire de 2'000 fr. est mis à la charge des recourants, solidairement entre eux.
3. Le présent arrêt est communiqué au mandataire des recourants, au Service de la population et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 16 novembre 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Vianin