Sachverhalt:
A. X._ und Y._ betrieben die Erotiketablissements A._, B._, C._ und D._. Im Januar 2002 führte die Eidgenössische Steuerverwaltung bei den beiden Betreibern eine Kontrolle durch. Gestützt auf deren Ergebnis wurden diese für den Betrieb der Etablissements rückwirkend für die Zeit vom 1. Januar 1996 bis 30. Juni 2000 (1. Quartal 1996 bis 2. Quartal 2000) als einfache Gesellschaft ins Register der Mehrwertsteuerpflichtigen eingetragen. Zudem erhob die Eidgenössische Steuerverwaltung mit Ergänzungsabrechnung vom 31. Januar 2002 eine Steuernachforderung von Fr. 446'117.--, zuzüglich Verzugszins. Die Nachforderung umfasste einerseits die bislang nicht entrichtete Mehrwertsteuer auf den verbuchten Umsätzen im Betrag von Fr. 203'179.60 und andererseits einen ermessensweise ermittelten Steuerbetrag von Fr. 242'938.30. Letzterer wurde damit begründet, dass der formelle Zustand der Geschäftsbücher mangelhaft sei und die einfache Gesellschaft Erlöse, welche in indirekter Stellvertretung erzielt worden seien, nur teilweise verbucht habe. Die Ergänzungsabrechnung wurde wegen eines Berechnungsfehlers mit Gutschriftsanzeige vom 4. Februar 2002 im Betrag von Fr. 1'535.-- korrigiert.
Am 10. Oktober 2002 bestätigte die Eidgenössische Steuerverwaltung die korrigierte Nachforderung im Betrag von Fr. 444'582.--. Betreffend die schätzungsweise festgelegten Erlöse hielt sie indessen dafür, die im Etablissement tätigen Frauen seien als unselbständig und nicht als selbständig erwerbend zu qualifizieren. Diese "formelle Ergänzung" habe auf den Steuerbetrag jedoch keinen Einfluss. Eine von X._ und Y._ dagegen gerichtete Einsprache wurde am 4. Januar 2006 abgewiesen. Ihre gegen diesen Einspracheentscheid bei der Eidgenössischen Steuerrekurskommission erhobene Beschwerde wurde am 7. Februar 2007 vom Bundesverwaltungsgericht übernommen. Dieses hiess die Beschwerde wegen Verjährung der Steuerforderung für das Jahr 1996 teilweise gut (d.h. im Betrag von Fr. 127'634.80: Fr. 57'435.65 verbuchte Einnahmen + Fr. 70'199.15 geschätzter Umsatz) und hob den Einspracheentscheid in diesem Umfang auf.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen die inzwischen geschiedenen X._ und Y._ dem Bundesgericht, das Urteil des Bundesverwaltungsgerichts vom 30. April 2008 aufzuheben und festzustellen, dass sie für das von den Prostituierten vereinnahmte Entgelt nicht mehrwertsteuerpflichtig seien. Eventuell sei die Steuer auf Fr. 146'014.-- festzusetzen.
Das Bundesverwaltungsgericht hat auf eine Vernehmlassung verzichtet.
Die Eidgenössische Steuerverwaltung beantragt, die Beschwerde abzuweisen.
C. Mit Verfügung vom 10. Juli 2008 erkannte der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zu.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 4. Juni 2008 beantragt die Eidgenössische Steuerverwaltung dem Bundesgericht, den Entscheid des Bundesverwaltungsgerichts vom 30. April 2008 aufzuheben, soweit dieser die Beschwerde der beiden Steuerpflichtigen gutgeheissen habe, und den Einspracheentscheid zu bestätigen.
X._ und Y._ beantragen, die Beschwerde abzuweisen.
Das Bundesverwaltungsgericht hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Die beiden Beschwerden richten sich gegen dasselbe Urteil, welches die gleichen Parteien und denselben Sachverhalt betrifft; es rechtfertigt sich daher, die beiden Verfahren (2C_432/2008 und 2C_426/2008) zu vereinigen und in einem Urteil zu erledigen.
1.2 Der angefochtene Endentscheid des Bundesverwaltungsgerichts in einer Angelegenheit des öffentlichen Rechts fällt unter keinen Ausschlussgrund und kann daher an das Bundesgericht weitergezogen werden; die Steuerpflichtigen und die Eidgenössische Steuerverwaltung sind zur Beschwerde legitimiert (<ref-law>).
1.3 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht geltend gemacht werden (<ref-law>). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.4 Der zu beurteilende Sachverhalt verwirklichte sich in den Jahren 1996 bis 2000. In materieller Hinsicht bleibt damit die Verordnung vom 22. Juni 1994 über die Mehrwertsteuer (MWSTV) anwendbar (Art. 93 und 94 MWSTG; SR 641.20).
2. 2.1 Der Mehrwertsteuer unterliegen u.a. die im Inland gegen Entgelt erbrachten Lieferungen von Gegenständen und Dienstleistungen (Art. 4 lit. a und b MWSTV). Als Dienstleistung gilt jede Leistung, die keine Lieferung eines Gegenstands ist (<ref-law>).
2.2 Steuerpflichtig ist, wer eine mit der Erzielung von Einnahmen verbundene gewerbliche oder berufliche Tätigkeit selbständig ausübt, auch wenn die Gewinnabsicht fehlt, sofern seine Leistungen im Inland jährlich gesamthaft Fr. 75'000.-- übersteigen (<ref-law>).
Mit der selbständig ausgeübten Tätigkeit müssen Einnahmen erzielt werden und sie muss auf eine gewisse Dauer ausgerichtet sein. Indizien für die selbständige Ausübung der Tätigkeit sind insbesondere das Tragen des unternehmerischen Risikos (Gewinn und Verlust), das Handeln und Auftreten in eigenem Namen gegenüber Dritten, die Wahlfreiheit, eine Aufgabe anzunehmen oder nicht und diese selbständig organisieren zu können. Daneben können die Beschäftigung von Personal, die Vornahme erheblicher Investitionen, eigene Geschäftsräumlichkeiten, verschiedene und wechselnde Auftraggeber sowie die betriebswirtschaftliche und arbeitsorganisatorische Unabhängigkeit eine Rolle spielen. Ob eine Tätigkeit als selbständig oder unselbständig anzusehen ist, bestimmt sich stets aufgrund einer umfassenden Würdigung sämtlicher einschlägiger Faktoren (Urteil 2C_518/2007 bzw. 2C_519/2007 vom 11. März 2008 E. 2.1 f.).
2.3 Steuerpflichtig sind gemäss <ref-law> auch Personengesamtheiten ohne Rechtsfähigkeit, die unter gemeinsamer Firma Umsätze tätigen. Ob dabei die einzelnen Personen dieser Gemeinschaft selbständig steuerpflichtig sind oder als unternehmerische Einheit gelten, bestimmt sich u.a. nach dem gemeinsamen Auftritt nach aussen (Urteil 2C_518/2007 bzw. 2C_519/2007 vom 11. März 2008 E. 2.3).
3. 3.1 Die Beschwerdeführer haben in der massgeblichen Zeit ein bis fünf Erotiketablissements (im Jahre 1996 fünf, Ende 1997 drei, Ende 1998 zwei und Ende 1999 noch eines) betrieben. Der Grossteil der Einnahmen stammte aus dem A._ in Zürich. Die Beschwerdeführer stellten den in ihren Etablissements tätigen Frauen nach eigenen Angaben gegen Entgelt ihre Infrastruktur (u. a. die Räumlichkeiten, wo sich die Kunden und Frauen kennen lernen können, die verschiedenen Zimmer und die Einrichtungen für das Inkasso) zur Verfügung.
3.2 Nach den von beiden Betreibern unterzeichneten Jahresabschlüssen betrugen ihre Einnahmen (inklusive Betriebsmittelverkäufe, exklusive Liegenschaftsvermietung und Zinserträge) im Jahre 1996 Fr. 941'061.--, im Jahre 1997 Fr. 894'612.--, im Jahre 1998 Fr. 576'330.--, im Jahre 1999 Fr. 523'236.-- und vom 1. Januar bis 30. Juni 2000 Fr. 278'974.--. Diese Einkünfte wurden in Folge der nachträglichen Eintragung der Betreiber als einfache Gesellschaft mit einer Steuer von Fr. 203'179.60 belegt, was von den Betreibern schon vor der Vorinstanz nicht grundsätzlich beanstandet wurde; sie verlangten einzig die Berücksichtigung der "Vorsteuern laut Schätzung", womit sich dieser Steuerbetrag auf Fr. 146'014.-- (vgl. Eventualbegehren) ermässigt hätte.
3.3 Die Vorinstanz hat den Vorsteuerabzug nicht zugelassen, weil die Betreiber keine Belege für deren Nachweis beigebracht haben (angefochtenes Urteil E. 4.3). Mit diesen Ausführungen setzen sich die Betreiber in ihrer Beschwerde nicht auseinander, weshalb auf den Eventualantrag nicht einzutreten ist. Im Übrigen ist der Vorsteuerabzug sogar im Rahmen einer Ermessenstaxation von einem strikten Nachweis durch den Mehrwertsteuerpflichtigen abhängig; eine ermessensweise Bestimmung des Vorsteuerabzuges ist in jedem Fall ausgeschlossen (Urteil 2C_356/2008 vom 21. November 2008 E. 4.3, mit Hinweisen).
3.4 Der pauschale Einwand der Betreiber, die Prostitution (Dirnenlohn) könne als sittlich missbilligtes Geschäft nicht Gegenstand der Mehrwertsteuer bilden, widerspricht der schweizerischen Rechtspraxis, die ausgehend vom Grundsatz der steuerlichen Wertneutralität selbst Umsätze aus illegalen Tätigkeiten der Mehrwertsteuer unterstellt (Urteil 2C_16/2008 vom 16. Mai 2008 E. 5, betreffend Betäubungsmittel). Der Hinweis der Betreiber auf Camenzind und andere (Handbuch zum Mehrwertsteuergesetz [MWSTG], 2. Aufl., 2003, Rz. 176) ist zudem nicht einschlägig, da der dort erwähnte Entscheid des Europäischen Gerichtshofes nicht das schweizerische sondern das EU-Recht betrifft. Überdies hat sich das Bundesgericht im Entscheid 2C_16/2008 mit diesem Urteil befasst, worauf verwiesen werden kann. Das Bundesgericht hat im Übrigen die Besteuerung von Erotik-Salons als zulässig erklärt (vgl. Urteile 2C_518/2007 bzw. 2C_519/2007 vom 11. März 2008).
4. 4.1 Streitig ist hauptsächlich, ob auch die Umsätze aus den erotischen Dienstleistungen, welche die in den Etablissements tätigen Frauen erzielten, mehrwertsteuerlich den Beschwerdeführern als Betreiber zuzuordnen sind. Die Beschwerdeführer stellen dies in Abrede mit der Begründung, die Prostituierten seien einer selbständigen Tätigkeit nachgegangen.
4.2 Die Vorinstanz hat dazu festgestellt, die Beschwerdeführer würden in verschiedenen Zeitschriften für ihre Etablissements bzw. für die Damen werben und dabei auf das Sexangebot hinweisen. Eine bei den Akten liegende Rechnung der Ringier AG verdeutliche, dass die Beschwerdeführer jeweils im eigenen Namen (des Etablissements) die Dienstleistungen anpriesen; Rechnungsempfängerin sei die Beschwerdeführerin per Adresse Salon A._. Ein ebenfalls aktenmässig erfasstes Inserat weise darauf hin, dass eine telefonische Voranmeldung unerlässlich sei. Die Kontaktaufnahme sei ausschliesslich über die Handy-Nummer der Beschwerdeführerin möglich gewesen. Eine direkte Kontaktnahme mit der Sexarbeiterin ohne Zuhilfenahme der Beschwerdeführer sei dem Kunden verwehrt geblieben. Es lägen generell keine Hinweise bzw. Belege (namentlich auf Damen ausgestellte Rechnungen, Geschäftspapiere mit eigenem Briefkopf, eigene Prospekte usw.) dafür vor, dass die Frauen nach aussen als selbständige Unternehmerinnen, unter eigener Firma, in Erscheinung getreten seien. Die anlässlich der Kontrolle vorgefundenen Kredit- und EC-Karten-Abrechnungsbelege von verschiedenen Parties trügen die Aufschrift "Rest. Betrieb S.A.P 8003 Zürich", wobei die Zahlungen unbestrittenermassen über das Konto der Beschwerdeführer erfolgt seien.
Nach den Feststellungen der Vorinstanz haben die Beschwerdeführer mehrmals wöchentlich Parties angeboten, wobei sie auch die jeweiligen Tarife festgelegt hätten. In den Pauschalbeträgen seien sämtliche sexuellen Dienstleistungen während der Party inbegriffen gewesen. Der Umsatz sei dabei nach einem bestimmten Schlüssel auf die anwesenden Damen verteilt worden. Diese hätten demnach die genauen Preise für die jeweils konkret erbrachten Leistungen in keiner Weise mitbestimmen können. Es sei durchaus möglich, dass die Preise gegenüber denjenigen im Einzelservice stark verbilligt seien. Jedenfalls habe die Preisvorgabe der Beschwerdeführer die betriebswirtschaftliche Unabhängigkeit der Frauen beeinträchtigt.
Die Damen seien auch in einer weitgehenden arbeitsorganisatorischen Abhängigkeit zu den Beschwerdeführern gestanden. Denn es hätten jeweils mehrere Frauen die Infrastruktur und die weiteren Betriebsmittel gleichzeitig oder nacheinander für ihre Sexangebote genutzt. Zudem hätten die Beschwerdeführer die Öffnungszeiten der Etablissements bzw. die Dauer der Parties festgelegt. Umfang und Zeitpunkt der Leistungserbringung der einzelnen Damen sei folglich direkt von der Belegungsdichte der beschwerdeführerischen Betriebsmittel abhängig gewesen. Leistungsumfang und -zeit hätten die Sexarbeiterinnen dementsprechend nur bedingt frei wählen können. Sie hätten sich vielmehr nach Massgabe der betrieblichen Möglichkeiten und weitgehend auch der Bedürfnisse bzw. des Willens der Beschwerdeführer bestimmt. Es habe im ureigensten Interesse der Beschwerdeführer gestanden, die Zimmer bestmöglich auszulasten und Friktionen weitestgehend zu vermeiden, weshalb sich die Damen zwangsläufig einer entsprechenden betrieblichen Ordnung der Beschwerdeführer hätten unterziehen müssen. So seien die Anwesenheiten der Sexarbeiterinnen wohl darauf hin ausgerichtet worden, die Bedürfnisse der Kunden bestmöglich abzudecken und so eine möglichst hohe Auslastung der Etablissements zu erreichen.
4.3 Die Beschwerdeführer rügen eine Verletzung von <ref-law>. Diese erblicken sie darin, dass die Vorinstanz von willkürlichen Sachverhaltsannahmen ausgehe. Insbesondere sei die Vorinstanz ihrer Abklärungspflicht nicht nachgekommen, weshalb sie auch den Anspruch der Beschwerdeführer auf rechtliches Gehör (<ref-law>) verletzt habe.
4.3.1 Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Abs. 2). Die Voraussetzungen für eine Sachverhaltsrüge nach <ref-law> und für eine Berichtigung des Sachverhalts von Amtes wegen nach <ref-law> stimmen im Wesentlichen überein. Soweit es um die Frage geht, ob der Sachverhalt willkürlich oder unter verfassungswidriger Verletzung einer Verfahrensregel ermittelt worden ist, sind strenge Anforderungen an die Begründungspflicht der Beschwerde gerechtfertigt. Entsprechende Beanstandungen sind vergleichbar mit den in <ref-law> genannten Rügen. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift darzulegen, inwiefern diese Feststellungen willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sind. Andernfalls können Vorbringen mit Bezug auf einen Sachverhalt, der von den Feststellungen im angefochtenen Entscheid abweicht, nicht berücksichtigt werden. Vorbehalten bleiben offensichtliche Sachverhaltsmängel im Sinne von <ref-law>, die dem Richter geradezu in die Augen springen (<ref-ruling> E. 1.4.3).
4.3.2 Die Beschwerdeführer bringen verschiedene Tatsachen vor (Aushandeln des Preises mit der Prostituierten und direkte Bezahlung an diese bei Barzahlung, blosse Inkassohilfe bei Kreditkartenbezahlung, tage- oder wochenweise Abrechnung, Bezahlung des Partyentgelts an eine Partyteilnehmerin, ununterbrochene tägliche Tätigkeit der Beschwerdeführerin selber als Sexarbeiterin im Etablissement A._). Diese Vorbringen erschöpfen sich indessen in einer Darlegung ihrer eigenen, nicht näher belegten Sicht der Dinge und lassen die Feststellungen der Vorinstanz nicht als unhaltbar erscheinen.
4.3.3 Nach den gesamten Umständen entspricht das von den Beschwerdeführern betriebene Gewerbe jenem, das den vom Bundesgericht am 11. März 2008 beurteilten Fällen 2C_518/2007 und 2C_519/2007 zu Grunde lag. Auch in jenen Fällen boten Prostituierte in Erotik-Studios Dritten ihre Dienstleistungen an, wofür ihnen neben Gemeinschaftsräumlichkeiten Zimmer mit der erforderlichen Infrastruktur und die für die Ausübung dieser Tätigkeit erforderlichen Utensilien, Hilfsmittel und Getränke zur Verfügung gestellt wurden; die Damen hatten 40 % ihres Umsatzes den Betreibern abzuliefern. Das Bundesgericht kam unter Berücksichtigung aller Umstände nach Massgabe des Grundsatzes der Unternehmenseinheit zum Schluss, die von den Prostituierten erzielten Umsätze seien den Betreibern zuzurechnen. Im Wesentlichen wurde darauf abgestellt, dass die Prostituierten nicht im eigenen Namen oder sonst direkt gegen aussen in Erscheinung traten.
Nachdem sich das von den Beschwerdeführern gewählte Betriebskonzept nicht in erkennbarer Weise von dem jenen Fällen zu Grunde liegenden, allgemein üblichen und notorischen Geschäftsgebaren von Erotiketablissements unterschied, durfte die Vorinstanz auch in zulässiger antizipierter Beweiswürdigung und damit ohne Verletzung von <ref-law> von der Erhebung weiterer Beweise absehen. Die Beschwerdeführer legen auch weder dar, welche Gepflogenheiten in den Salons der Beschwerdeführer nicht abgeklärt worden sein sollen, noch inwiefern die entsprechenden Erkenntnisse für den Ausgang des Verfahrens entscheidend sein könnten.
4.4 Die Vorinstanz durfte auf Grund ihrer somit verbindlichen Feststellungen ohne Verletzung von Bundesrecht davon ausgehen, dass die in den Räumlichkeiten der Beschwerdeführer angebotenen sexuellen Dienstleistungen aufgrund des nach aussen sichtbaren Erscheinungsbildes einen integrierten Zweig der Erotiketablissements der Beschwerdeführer darstellten und damit auch die Umsätze der einzelnen Prostituierten den Beschwerdeführern mehrwertsteuerlich zuzurechnen sind (vgl. Urteile 2C_518/2007 und 2C_519/2007 vom 11. März 2008).
4.5 Soweit die Beschwerdeführer rügen, sie würden gesetzwidrig für ein Entgelt besteuert, das sie nicht erzielt hätten, verkennen sie, dass sich bei Personenmehrheiten die Steuerpflicht des Einzelnen nach dem gemeinsamen Auftritt nach aussen bestimmt; danach gelten die Beschwerdeführer zusammen mit allen in ihren Etablissements tätigen Prostituierten als Unternehmenseinheit. Auch der Umstand, dass die Beschwerdeführer die Steuer nicht auf den Verbraucher überwälzen können, steht dem nicht entgegen (vgl. Urteile 2C_518/2007 und 2C_519/2007 vom 11. März 2008 E. 3.4).
4.6 Wie das Führen der hier in Frage stehenden Etablissements unter strafrechtlichen Gesichtspunkten zu betrachten ist, ist hier nicht zu entscheiden. Es kann jedenfalls nicht die Rede davon sein, dass die Beschwerdeführer mit der in rein steuerrechtlicher Betrachtungsweise erfolgten Zurechnung aller in den Etablissements erzielten Einkünfte der Förderung der Prostitution beschuldigt würden.
5. 5.1 Die Beschwerdeführer haben unbestrittenermassen die von den Prostituierten vereinnahmten Entgelte nirgends in ihrer Buchhaltung bzw. ihren Geschäftsbüchern und -unterlagen erfasst. Auch haben sie der Eidgenössischen Steuerverwaltung diesbezüglich keinerlei Belege vorgelegt. Dass damit der in Frage stehende Umsatz durch Schätzung zu ermitteln war, beanstanden die Beschwerdeführer zu Recht nicht. Dasselbe gilt für die Annahme, der seitens der Beschwerdeführer verbuchte, von den Damen als Entschädigung für die Infrastrukturbenützung abzuliefernde Umsatzanteil entspreche 45 % des Gesamtumsatzes aus der Erbringung erotischer Dienstleistungen. Nach eigener Darstellung hat sie sich dabei einerseits auf ihr vorliegende Angaben von anderen Steuerpflichtigen, welche im gleichen Bereich tätig sind, sowie andererseits auf mündliche Aussagen der Sittenpolizei Zürich gestützt. Demnach mache der von den Prostituierten an das jeweilige Etablissement abzuliefernde Umsatzanteil in vergleichbaren Einrichtungen regelmässig 40 - 45 % des Gesamtumsatzes aus.
5.2 Sind, wie im vorliegenden Fall, die Voraussetzungen einer Ermessenstaxation erfüllt, ist das Bundesgericht an diese Einschätzung gebunden, wenn sie auf einer richtigen und vollständigen Tatbestandsermittlung und auf einer sachgemässen Abwägung der Gesamtheit der für die Veranlagung massgebenden Verhältnisse beruht. Es prüft derartige Schätzungen nur mit Zurückhaltung auf offensichtliche Fehler und Irrtümer hin, wobei es dem Steuerpflichtigen obliegt, die Unrichtigkeit der Schätzung zu beweisen. Der Beschwerdeführer darf sich somit nicht darauf beschränken, die Kalkulationsgrundlagen der Ermessensveranlagung allgemein zu kritisieren; er muss vielmehr nachweisen, dass die von der Eidgenössischen Steuerverwaltung vorgenommene Schätzung offensichtlich falsch ist (vgl. etwa Urteil 2C_171/2008 vom 30. Juli 2008 E. 4.2).
Eine substanziierte Begründung sowie Belege, welche die offensichtliche Unrichtigkeit der Schätzung nachweisen könnten, bringen die Beschwerdeführer nicht vor. Insbesondere fehlt es an einem Nachweis für die Behauptung, die Beschwerdeführerin sei bis 2003 selber als Sexarbeiterin tätig gewesen und habe im Etablissement A._ mindestens 50 % zum verbuchten Umsatz beigetragen. Diese Behauptung durfte die Vorinstanz gestützt auf das in den Akten liegende Video eines Fernsehauftrittes der Beschwerdeführerin vom 6. April 2006 (Sendung "Aeschbacher") sowie ein Interview vom März 2006 ("Das Magazin" Nr. 10/2007) ohne Verletzung von Bundesrecht als reine Schutzbehauptung qualifizieren. Die Rüge der unzutreffenden Sachverhaltsfeststellung ist unbegründet.
5.3 Die Beschwerde der beiden Steuerpflichtigen ist aus diesen Gründen abzuweisen, soweit darauf einzutreten ist.
6. 6.1 Die Vorinstanz hat in teilweiser Gutheissung der Beschwerde erkannt, die Eidgenössische Steuerverwaltung habe mit ihrem Schreiben vom 18. Dezember 2001 nicht nur eine Steuerkontrolle angekündigt, sondern die Beschwerdeführer ausdrücklich darauf hingewiesen, allfällig seit dem 1. Januar 1996 noch geschuldete Steuern würden nachgefordert. Zudem sei das Schreiben als Einforderungshandlung im Sinne von Art. 40 und 41 MWSTV bezeichnet gewesen; in der Betreffzeile sei ausdrücklich auf die "Verjährungsunterbrechung" hingewiesen worden. Da der Sachverhalt, der zu einer Mehrwertsteuernachforderung führen werde, noch nicht nach allen Seiten abgeklärt sein müsse, um rechtsgültig die Verjährung unterbrechen zu können, sei dieses Schreiben grundsätzlich dazu geeignet gewesen, verjährungsunterbrechende Wirkung zu haben. Indes sei das eingeschrieben abgesandte Schreiben unbestritten nicht im Rahmen eines hängigen Verfahrens erfolgt, weshalb nicht ersichtlich sei, inwiefern die Beschwerdeführer auf Grund der Zustellfiktion mit der Zustellung eines behördlichen Akts seitens der Eidgenössischen Steuerverwaltung hätten rechnen müssen, zumal sie zu diesem Zeitpunkt noch nicht einmal im Register der Mehrwertsteuerpflichtigen eingetragen gewesen seien. Die Zustellung des Einschreibens vom 18. Dezember 2001 habe somit nicht fingiert werden können. Erst das Hinweisschreiben vom 8. Januar 2002, welchem das Einschreiben vom 18. Dezember 2001 beigelegt war, habe verjährungsunterbrechende Wirkung gehabt. Die Mehrwertsteuerforderung für die Zeit vom 1. Januar bis 31. Dezember 1996 sei deshalb verjährt. Dies gelte sowohl für den ermessensweise geschätzten Umsatz aus der Erbringung der erotischen Dienstleistungen als auch für die Nachforderung der verbuchten Einnahmen der Beschwerdeführer aus dem Betrieb der Etablissements.
6.2 Mit ihrer Beschwerde macht die Eidgenössische Steuerverwaltung demgegenüber geltend, die in Frage stehende Steuerforderung für das Jahr 1996 sei nicht verjährt. Sie rügt in diesem Zusammenhang eine Verletzung von Art. 40 Abs. 1 und 2 MWSTV.
6.3 Die Mehrwertsteuerforderung verjährt gemäss <ref-law> fünf Jahre nach Ablauf des Kalenderjahres, in dem sie entstanden ist. Der Lauf der Verjährungsfrist wird durch jede Einforderungshandlung unterbrochen (<ref-law>). Die Einforderungshandlung ist nach der bundesgerichtlichen Rechtsprechung an keine besondere Form gebunden. Der Begriff der Einforderungshandlung ist daher weit zu fassen: Verjährungsunterbrechende Wirkung kommt bereits der blossen Mitteilung zu, mit welcher eine spätere Veranlagung erst in Aussicht gestellt wird (vgl. <ref-ruling> E. 2 f.). Die Vorinstanz hat daher zu Recht erkannt, dem Schreiben komme - unter der Voraussetzung der rechtsgültigen Zustellung - verjährungsunterbrechende Wirkung zu. Dies wird denn auch von keiner Partei bestritten.
6.4 Eine Sendung gilt grundsätzlich in dem Moment als zugestellt, in welchem sie in den Machtbereich des Empfängers gelangt (<ref-ruling> E. 4b). Werden empfangsbedürftige behördliche Mitteilungen eingeschrieben versandt, so gelten sie im Zeitpunkt der Entgegennahme bzw. der Abholung auf der Post als zugestellt. Wird der Adressat bei der Zustellung nicht angetroffen und daher eine Abholeinladung in seinen Briefkasten oder sein Postfach gelegt, gilt die Sendung als in jenem Zeitpunkt zugestellt, in welchem sie tatsächlich auf der Post abgeholt wird; geschieht dies nicht innert der Abholfrist von sieben Tagen, gilt sie als am letzten Tag dieser Frist zugestellt, sofern der Adressat mit einer gewissen Wahrscheinlichkeit mit der Zustellung rechnen musste (vgl. <ref-ruling> E. 1.2.3, mit Hinweisen; vgl. auch <ref-law>).
6.5 Die Vorinstanz hat in diesem Zusammenhang erkannt, diese bundesgerichtliche Rechtsprechung gelte nur bei Zustellung von Mitteilungen während eines hängigen Verfahrens. Diese Voraussetzung sei hier indessen nicht erfüllt, weshalb die Zustellung nicht fingiert werden könne.
Die Eidgenössische Steuerverwaltung macht mit ihrer Beschwerde geltend, für die Zustellung eines einfachen Unterbrechungsschreibens sei allein der Zeitpunkt der nachweisbaren Postaufgabe (Sendeprinzip) massgebend; die Frage der Zustellfiktion stelle sich damit gar nicht.
6.6 Nach dem Wortlaut von <ref-law> setzt die Unterbrechung der Verjährung lediglich eine Einforderungshandlung durch die zuständige Behörde voraus. Eine Kenntnisnahme derselben durch den Steuerpflichtigen wird nicht verlangt. Die Unterbrechung gilt denn auch gegenüber allen Zahlungspflichtigen (Abs. 3).
6.6.1 Im Privatrecht wird die Verjährung u.a. durch Schuldbetreibung, durch Klage oder durch Einrede vor einem Gericht oder Schiedsgericht sowie durch Eingabe im Konkurs und Ladung zu einem amtlichen Sühneversuch unterbrochen (<ref-law>). Für die Unterbrechung genügt in all diesen Fällen die Postaufgabe, da diese Unterbrechungsgründe allein auf eine Handlung des Forderungsgläubigers (<ref-ruling> E. 3) abstellen; nicht vorausgesetzt wird, dass der Schuldner davon Kenntnis erhält (<ref-ruling> E. a).
6.6.2 Der Begriff der verjährungsunterbrechenden Handlung ist im öffentlichen Recht weiter gefasst als im Privatrecht. Während es im Privatrecht zur Unterbrechung der Verjährung in der Regel qualifizierter Rechtshandlungen bedarf, bestehen diesbezüglich im öffentlichen Recht erleichterte Möglichkeiten. Im Verwaltungsrecht kann schon die blosse Mitteilung einer Forderung oder die Zustellung einer formellen Mahnung und erst recht jede behördliche Einforderungshandlung, d.h. jede amtliche Handlung in einem Verwaltungs- oder Verwaltungsstreitverfahren die Verjährung unterbrechen (Urteil 2A.319/2002 vom 6. Dezember 2002 E. 2.3); es genügen dazu namentlich einfache schriftliche Erklärungen (<ref-ruling> E. 4.3.1, mit zahlreichen Hinweisen auf Rechtsprechung und Literatur).
Im Steuerrecht ist als Einforderungshandlung, welche die Verjährung unterbricht, jede dem Steuerpflichtigen zur Kenntnis gebrachte, auf Einforderung oder auf Feststellung des Steueranspruchs gerichtete Amtshandlung der Steuerbehörde zu verstehen; dazu zählen etwa die Zustellung des Steuererklärungsformulars, die Mahnung zur Einreichung einer Steuererklärung, die Ankündigung oder Vornahme von Bücheruntersuchungen, die Eröffnung einer definitiven oder provisorischen Steuerveranlagung sowie die Aufforderung oder Mahnung zur Zahlung. Insbesondere ist aber keine der in <ref-law> vorgesehenen Handlungen erforderlich; zur Unterbrechung der Verjährung genügt jede Mitteilung der Steuerverwaltung an den Steuerpflichtigen, dass sie einen bestimmten Tatbestand als steuerpflichtig erachtet (Urteil 2A.227/1996 vom 26. September 1997 E. 3; vgl. auch Urteil des Eidg. Versicherungsgerichts B.27/00 vom 10. Oktober 2001 E. 8c, publ. in: SZS 2003 S. 49 ff.). Diese muss, um als massgebender Unterbrechungsakt bezeichnet zu werden, nach aussen in Erscheinung getreten sein, was mit der nachweisbaren Postaufgabe der Fall ist (vgl. <ref-ruling> E. 4.4). Nicht erforderlich für die Wirksamkeit des Aktes ist hingegen die Kenntnisnahme durch den Empfänger.
Die Wirkung der Unterbrechung tritt somit in denjenigen Fällen, in welchen die Unterbrechung der Verjährung durch formloses Schreiben bewirkt werden kann, mit der Postaufgabe des Schreibens ein (vgl. <ref-ruling> E. 4.4). Das Bundesgericht hat es denn auch als genügend erachtet, dass die Mitteilung per Fax erfolgt ist (Urteil 2A.546/2001 vom 1. Mai 2002 E. 3e). In einem weiteren Fall hat das Bundesgericht ebenfalls die Annahme, die Verjährungsfrist für öffentlich-rechtliche Gebühren werde gewahrt bzw. unterbrochen, wenn die Zahlungsaufforderung am letzten Tag der Frist der Post übergeben wurde, als nicht willkürlich und nicht im Widerspruch mit der bundesgerichtlichen Praxis erachtet (Urteil 2P.458/1996 vom 14. Juli 1997 E. 2).
Diese Auslegung lässt sich insbesondere damit begründen, dass die Verjährungsunterbrechung im Steuerrecht die Kenntnis derselben durch den Steuerpflichtigen nicht voraussetzt. Denn diesem steht gegen die Unterbrechungshandlung kein Rechtsmittel zu Verfügung; er kann die Verjährung der Steuerforderung erst im Zusammenhang mit der Veranlagung geltend machen. Der Steuerpflichtige wird durch die Unterbrechungshandlung auch nicht zu bestimmten Vorkehren gezwungen, deren Unterlassung sich zu seinen Ungunsten auswirken könnte; insbesondere kommt ihr keine fristauslösende Wirkung zu. Lässt die bundesgerichtliche Rechtsprechung im Bereich des formstrengen Privatrechts die Postaufgabe als verjährungsunterbrechende Handlung genügen, so muss dies erst recht im öffentlichen Recht und insbesondere im Steuerrecht gelten. Dies besonders in einem Massenverfahren, welches wie die Mehrwertsteuer auf dem Grundsatz der Selbstveranlagung beruht und in welchem der Steuerverwaltung lediglich Bezugs- und Kontrollfunktionen zukommen. Es würde hier dem Sinn und Zweck von <ref-law> widersprechen, der Steuerverwaltung einerseits eine Unterbrechung der Verjährung durch blosse formlose Mitteilung zu ermöglichen, und andererseits - und ohne dass der Wortlaut dies nahelegen würde - zusätzlich deren Kenntnisnahme durch den Steuerpflichtigen zu verlangen.
6.7 Die Beschwerde der Eidgenössischen Steuerverwaltung ist daher gutzuheissen und der angefochtene Entscheid aufzuheben, soweit damit der Einspracheentscheid der Eidgenössischen Steuerverwaltung aufgehoben wird. Die Beschwerdegegner haben somit ebenfalls die Kosten des vorinstanzlichen Verfahrens vollumfänglich zu tragen; zudem ist ihnen keine Parteientschädigung zuzusprechen (Art. 67 und Art. 68 Abs. 5 BGG).
7. Da die Beschwerdeführer bzw. Beschwerdegegner in beiden Verfahren unterliegen, haben sie die gesamten Kosten des Verfahrens vor Bundesgericht unter solidarischer Haftung zu tragen (Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Verfahren 2C_432/2008 und 2C_426/2008 werden vereinigt.
2. Die Beschwerde im Verfahren 2C_432/2008 wird abgewiesen, soweit darauf einzutreten ist.
3. Die Beschwerde im Verfahren 2C_426/2008 wird gutgeheissen und der Entscheid des Bundesverwaltungsgerichts vom 30. April 2008 in dem Umfang aufgehoben, als er den Einspracheentscheid der Eidgenössischen Steuerverwaltung vom 4. Januar 2006 aufhebt.
4. In Abänderung von Ziff. 2 und 3 des angefochtenen Entscheides werden X._ und Y._ die Kosten des vorinstanzlichen Verfahrens von Fr. 6'000.-- vollumfänglich auferlegt. Es wird ihnen für das vorinstanzliche Verfahren keine Parteientschädigung zugesprochen.
5. Die Gerichtskosten beider Verfahren vor Bundesgericht von insgesamt Fr. 12'000.-- werden X._ und Y._ auferlegt, unter solidarischer Haftung
6. Dieses Urteil wird den Parteien und dem Bundesverwaltungsgericht, Abteilung I, schriftlich mitgeteilt.
Lausanne, 18. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Küng