Faits:
A. Par jugement du 2 mars 2007, le Tribunal correctionnel de l'arrondissement de l'Est vaudois a notamment condamné X._ pour vol, vol en bande, tentative de vol en bande, brigandage, tentative de contrainte, contrainte sexuelle, dommages à la propriété, violation de domicile, recel, violence ou menace contre les autorités et les fonctionnaires, vol d'usage d'un bateau, infraction et contravention à la LStup à une peine privative de liberté de trois ans.
Le recours de X._ a été partiellement admis par la Cour de cassation pénale du Tribunal cantonal vaudois le 22 octobre 2007. Cette autorité a libéré X._ du chef d'accusation de violation de domicile dans trois cas concernant des bateaux. Elle n'a, par ailleurs, retenu que la tentative de violence ou menace contre les autorités ou les fonctionnaires. Cela fait, elle a fixé la durée de la peine privative de liberté à trente-quatre mois.
Saisi par X._ d'un recours en matière pénale dirigé contre cette décision, le Tribunal fédéral l'a annulée, par arrêt du 22 janvier 2009 (6B_303/2008). La cause a été renvoyée à l'autorité cantonale pour qu'elle complète les constatations de fait relatives à l'intensité de l'attouchement commis par le recourant sur les seins d'une victime le 25 janvier 2006 et qu'elle détermine si ce comportement constituait une contrainte sexuelle ou une contravention contre l'intégrité sexuelle.
B. Par arrêt du 23 mars 2009, la Cour de cassation pénale du canton de Vaud a partiellement admis le recours de X._. Elle n'a pas retenu la contrainte sexuelle mais la contravention contre l'intégrité sexuelle au sens de l'<ref-law>. Statuant à nouveau, la cour cantonale a condamné le recourant à trente-trois mois et demi de privation de liberté, soit quinze jours de moins que la peine précédemment fixée.
C. X._ forme un recours en matière pénale contre cet arrêt. Il conclut à sa réforme, soit à libération du chef d'accusation de la contravention contre l'intégrité sexuelle ainsi qu'au prononcé d'une peine privative de liberté de deux ans au plus, avec sursis. A titre subsidiaire, il conclut au prononcé d'une peine privative de liberté inférieure à trente-trois mois et quinze jours, avec sursis partiel, la partie à exécuter n'étant pas supérieure à la détention préventive subie. Il sollicite, par ailleurs, l'assistance judiciaire.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit:
1. Le recourant invoque toute d'abord une violation de l'ancien <ref-law>. Il prétend que cette disposition constituerait une lex specialis par rapport à l'ancien <ref-law>. Cette dernière norme, son al. 3 en particulier, ne s'appliquerait donc pas et la contravention à l'<ref-law> serait prescrite. Le recourant souligne, dans ce contexte, que l'infraction en question, commise le 25 janvier 2006, aurait été prescrite le 25 janvier 2009 soit avant que la Cour de cassation pénale vaudoise ne prononce, le 23 mars 2009, sa condamnation pour contravention contre l'intégrité sexuelle.
1.1 Les dispositions en matière de prescription figurant aux anciens <ref-law> ont été modifiées par la loi du 5 octobre 2001, entrée en vigueur le 1er octobre de l'année suivante (RO 2002 2993, 2996). Avec la révision de la partie générale du code pénal, entrée en vigueur au 1er janvier 2007 (RO 2006 3459), les règles sur la prescription figurent désormais, sans nouvelle modification, aux <ref-law>. Ce droit n'est donc pas plus favorable, sur ce point, à celui en vigueur au moment des faits, en janvier 2006, que la cour cantonale a appliqué à juste titre (<ref-law>).
1.2 Contrairement aux normes en vigueur avant le 1er octobre 2002, les nouvelles ne prévoient plus la suspension et l'interruption de la prescription et suppriment la notion de prescription absolue, tout en fixant des délais plus longs. Désormais, le délai de prescription ne court plus si, avant son échéance, un jugement de première instance est rendu (ancien <ref-law>; <ref-law>) et qu'il porte condamnation (<ref-ruling> consid. 2.1, p. 330 s.).
Le Tribunal fédéral a déjà eu l'occasion de juger qu'en raison du renvoi de l'<ref-law> (ancien <ref-law>) aux dispositions de la première partie du code et du fait que l'<ref-law> (ancien et nouveau) ne fixe qu'un délai de prescription plus court pour les contraventions, les règles générales des <ref-law> (anciens <ref-law>) s'appliquent aussi aux contraventions. Il en va notamment ainsi de la norme selon laquelle la prescription ne court plus si, avant son échéance, un jugement de première instance a été rendu (v. arrêts non publiés des 22 septembre 2009, 6B_373/2009, consid. 2.3 et 16 juillet 2009, 6B_186/2009, consid. 2.3; v. déjà arrêt non publié du 2 mai 2005, 6P.182/2004, consid. 3.3, à propos de l'ancien <ref-law>). Le grief déduit de la spécialité de l'<ref-law> est infondé.
2. Le recourant invoque ensuite une violation de l'<ref-law>. Il estime que, compte tenu de l'abandon de la qualification de contrainte sexuelle au bénéfice de la contravention réprimée par l'<ref-law>, la peine privative de liberté à laquelle il a été condamné n'aurait pas dû excéder deux ans. Le recourant soutient aussi que les juges cantonaux ont commis un déni de justice en ne réexaminant pas une éventuelle violation de l'<ref-law>.
2.1 L'autorité à laquelle la cause est renvoyée voit sa cognition limitée par les motifs de l'arrêt de renvoi, en ce sens qu'elle est liée par ce qui a été jugé définitivement par le Tribunal fédéral. Il n'est pas possible de remettre en cause ce qui a été admis (même implicitement) par ce dernier. L'examen juridique se limite aux questions laissées ouvertes par l'arrêt de renvoi, ainsi qu'aux conséquences qui en découlent ou aux problèmes qui leur sont liés (arrêt du 1er juillet 2009, 4A_158/2009, consid. 3.3 et les références citées ; Corboz, in Commentaire de la LTF, 2009, no 27 ad <ref-law>).
Dans l'arrêt de renvoi, le Tribunal fédéral, faute de pouvoir se prononcer sur la base des faits constatés, jugés lacunaires, a demandé de les compléter en relation avec l'intensité de l'attouchement porté sur les seins de la victime et, cela fait, de réexaminer la qualification juridique. L'autorité cantonale ayant finalement retenu une contravention à l'<ref-law> au lieu de la contrainte, cette décision avait un effet direct sur la mesure de la peine qui devait être fixée à nouveau. Contrairement à ce que prétend le recourant, la décision de renvoi ne demandait pas à l'autorité cantonale d'examiner si la mesure de la peine décidée dans son jugement du 22 octobre 2007 violait l'<ref-law>. L'arrêt de renvoi ne se prononce ni sur cette question ni sur celle du sursis. Il appartenait cependant à l'autorité cantonale de fixer une nouvelle peine et de réexaminer la question du sursis si elle admettait une nouvelle qualification juridique de l'infraction. Pour ce faire, la cour cantonale a donné la possibilité de s'exprimer sur la question de la peine et du sursis au recourant (cf. <ref-ruling>). Ce dernier s'est limité à se référer au recours qu'il avait déposé le 22 mars 2007 (arrêt entrepris, consid. E.b, p. 5). Il ne s'est prévalu d'aucun élément déterminant quant à sa situation personnelle actuelle dont l'autorité cantonale aurait omis de tenir compte et s'est limité à renvoyer aux reproches qu'il avait déjà formulés contre la mesure de la peine prononcée en première instance. Ces griefs avaient donc déjà été examinés par la cour cantonale dans son arrêt du 22 octobre 2007.
Par conséquent, la cour cantonale n'a commis aucun déni de justice en refusant d'examiner, dans ce contexte, une éventuelle violation de l'<ref-law> et en se limitant à prononcer une nouvelle peine en raison de la nouvelle qualification juridique opérée ensuite de l'arrêt de renvoi de la cour de céans.
2.2 L'<ref-law> correspond à l'ancien <ref-law> et à la jurisprudence y relative, laquelle conserve donc sa valeur (cf. arrêt 6B_472/2007 consid. 8.1 et les arrêts cités). Cette jurisprudence a été rappelée dans l'<ref-ruling> consid. 6.1 p. 20/21, auquel on peut se référer. Il suffit de relever que le juge dispose d'un large pouvoir d'appréciation. Il n'y a violation du droit fédéral que si la peine a été fixée en dehors du cadre légal, si elle repose sur des considérations étrangères à l'<ref-law>, si elle ne tient pas compte des critères découlant de cette disposition (abus du pouvoir d'appréciation) ou si le juge s'est montré à ce point sévère ou clément que l'on doive parler d'un excès dans l'exercice de ce pouvoir (<ref-ruling> consid. 2.1, p. 19).
2.3 Le recourant reproche à l'autorité cantonale de ne pas avoir suffisamment tenu compte du fait que, lors des vols commis en 2001 et des événements du 23 avril 2004, il s'était contenté de faire le guet.
Ce faisant, le recourant s'écarte de manière inadmissible (<ref-law>) des constatations de fait du jugement de première instance, auquel renvoie la décision entreprise (arrêt du 23 mars 2009, consid. B, p. 2) dont il ressort que, lorsque c'était le cas, le recourant ne s'est pas contenté de faire le guet, mais a pleinement participé à la commission des infractions en qualité de coauteur (jugement du Tribunal correctionnel, du 2 mars 2007, p. 22-27 et p. 38-39).
Au surplus, le recourant ne cite aucun critère qui aurait été retenu à tort par l'autorité cantonale ou qui aurait été ignoré et on ne discerne pas que tel soit le cas. La peine a été fixée dans le cadre légal. Aucune circonstance atténuante n'a été admise mais une circonstance aggravante, le concours (<ref-law>), est réalisée. Il n'y a donc pas d'abus du pouvoir d'appréciation.
Par ailleurs, même si la responsabilité du recourant est légèrement diminuée, compte tenu de la durée de la délinquance et de son importance et du fait qu'il n'y a pas de raison de penser qu'une peine moins sévère suffirait à le détourner de commettre d'autres infractions, la peine de trente-trois mois et demi prononcée en l'espèce ne procède pas non plus d'un excès du large pouvoir d'appréciation conféré aux autorités cantonales. Peu importe dès lors que la réduction opérée par la cour cantonale suite à la nouvelle qualification juridique donnée à une infraction paraisse insuffisante au recourant, dans la mesure où, dans son ensemble, la quotité de la peine prononcée ne viole pas le droit fédéral.
3. Invoquant les art. 42 et 43 CP, le recourant soutient que le tribunal aurait dû lui accorder le sursis complet, subsidiairement partiel, en raison d'un pronostic qui ne devrait pas être défavorable.
La peine infligée au recourant étant de trente-trois mois et demi, seul l'octroi du sursis partiel entre en ligne de compte (art. 42 et 43 CP).
3.1 L'<ref-law> prévoit que le juge peut suspendre partiellement l'exécution d'une peine pécuniaire, d'un travail d'intérêt général ou d'une peine pécuniaire d'un an au moins et de trois ans au plus afin de tenir compte de façon appropriée de la faute de l'auteur (al. 1). La partie à exécuter ne peut excéder la moitié de la peine (al. 2). En cas de sursis partiel à l'exécution d'une peine privative de liberté, la partie suspendue, de même que la partie à exécuter, doivent être de six mois au moins. Les règles d'octroi de la libération conditionnelle ne lui sont pas applicables (al. 3).
Les conditions subjectives permettant l'octroi du sursis (<ref-law>), à savoir les perspectives d'amendement, valent également pour le sursis partiel dès lors que la référence au pronostic ressort implicitement du but et du sens de l'<ref-law>. Ainsi, lorsque le pronostic quant au comportement futur de l'auteur n'est pas défavorable, la loi exige que l'exécution de la peine soit au moins partiellement suspendue. Mais un pronostic défavorable exclut tout sursis, même partiel. En effet, s'il n'existe aucune perspective que l'auteur puisse être influencé de quelque manière par un sursis complet ou partiel, la peine doit être entièrement exécutée (<ref-ruling> consid. 5.3.1, p. 10).
3.2 En l'occurrence, l'autorité inférieure a retenu un pronostic défavorable quant à l'octroi du sursis. L'arrêt cantonal du 23 mars 2009, qui rappelle brièvement les critères pris en compte, renvoie expressément aux considérants de l'arrêt du 22 octobre 2007. Ce dernier mentionne que le recourant a réitéré ses comportements délictueux à de nombreuses reprises, sans se soucier des diverses sanctions prises à son égard, dont il n'a manifestement tiré aucun enseignement. L'autorité cantonale souligne en particulier qu'elle a principalement tenu compte de l'importance des actes commis, de la durée de l'activité délictueuse, de la récidive et du fait que le recourant n'a fait aucun effort pour trouver un travail. Tous ces éléments sont pertinents pour l'examen de cette question.
3.3 Le recourant objecte, en invoquant la violation de son droit d'être entendu, que la cour cantonale n'aurait pas examiné si l'état de fait aurait dû être complété sur deux points. Il souligne, à ce propos, être au bénéfice d'un permis F et en déduit qu'on ne peut exiger de lui la même réinsertion sociale que les titulaires d'une autre autorisation en raison de ses possibilités restreintes de trouver un emploi. Il se réfère, par ailleurs, à une attestation des formateurs de la FAREAS produite aux débats. Ce document, qui témoigne de sa volonté de réinsertion, contredirait l'appréciation de l'autorité cantonale selon laquelle il n'a exercé aucune activité lucrative régulière depuis plusieurs années et n'a fait aucun effort pour trouver un travail.
3.4 Le droit d'être entendu, tel qu'il est garanti à l'art. 29 al. 2 Cst., comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuve pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 2.2 p. 504 s.; <ref-ruling> consid. 2b p. 56; <ref-ruling> consid. 3a p. 51 et les arrêts cités).
Dans le cas particulier, l'autorité cantonale est parvenue à la conclusion que le recourant n'avait fait qu'une démonstration de circonstance en s'inscrivant à un cours de la FAREAS peu avant l'audience des débats et qu'il n'a fait aucun effort, notamment pour trouver un travail. Le recourant ne motive aucune violation de son droit d'être entendu (<ref-law>). Il s'en prend en réalité à l'appréciation des juges cantonaux et la conteste en y opposant d'autres éléments du dossier.
Or, si le recourant entendait démontrer l'arbitraire de cette appréciation, il lui appartenait de le faire au niveau cantonal par un recours en nullité, ce qu'il n'a pas fait, ou d'établir l'arbitraire de ces constatations devant la cour de céans en motivant dûment ce grief (<ref-law>), ce qu'il ne fait pas non plus. Au demeurant, que le recourant soit au bénéfice d'un permis F ou l'attestation des formateurs de la FAREAS, où il s'est inscrit peu avant l'audience des débats alors qu'il s'agit de la seule activité qu'on lui connaisse depuis 2000 (arrêt de la cour cantonale du 22 octobre 2007 p. 25 auquel l'arrêt attaqué renvoie expressément en p. 9 consid. 5c), ne permettent pas de qualifier l'appréciation cantonale d'insoutenable. Il s'ensuit que le refus du sursis, même partiel, ne viole pas le droit fédéral.
4. Le recourant succombe. Ses conclusions étaient d'emblée vouées à l'échec. L'assistance judiciaire doit être refusée (<ref-law>). Il supporte les frais de la procédure (<ref-law>), qui peuvent être arrêtés en tenant compte de sa situation financière (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. L'assistance judiciaire est refusée.
3. Les frais judiciaires, arrêtés à 1600 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Cour de cassation pénale.
Lausanne, le 26 octobre 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Le Greffier:
Favre Vallat