Sachverhalt:
A. Die Genossenschaft Migros Aare ist Eigentümerin des Einkaufszentrums Gäu-Park in Egerkingen. Dieses besteht aus einem nördlichen und einem südlichen Komplex. Mit dem Gäu-Park verbunden ist das ehemalige Einkaufszentrum der Waro, das heute von der Coop genutzt wird. Unmittelbar an den südlichen Teil des Gäu-Parks grenzt das ehemalige Gebäude der Kaffeefilterproduzentin Melitta an. Es wurde nach Stilllegung des Betriebs gestützt auf eine Baubewilligung vom 17. Mai 2004 mit dem südlichen Teil des Gäu-Parks verbunden und dient seither als Verkaufsfläche für Non Food-Artikel.
Im Februar 2007 legte der Gemeinderat Egerkingen eine Änderung der Gestaltungspläne "Gäu Park und Waro Egerkingen" und "Gäu-Park 2" öffentlich auf. Die Änderung sollte den Bau eines zweiten Verbindungsgangs zwischen dem nördlichen und dem südlichen Gebäudekomplex ermöglichen. Der Verkehrs-Club der Schweiz (VCS) erhob dagegen Einsprache. Zugleich machte er geltend, die bereits früher erfolgte Umnutzung des Melitta-Gebäudes sei nicht korrekt erfolgt; er verlangte deshalb von der Gemeinde Egerkingen, dafür nachträglich ein Gestaltungsplanverfahren mit Umweltverträglichkeitsprüfung (UVP) durchzuführen.
Auf die erwähnten Gestaltungsplanänderungen wurde in der Folge verzichtet. Am 12. November 2009 lehnte die Baukommission der Gemeinde Egerkingen das Gesuch des VCS, für die Umnutzung des ehemaligen Melitta-Gebäudes ein neues Verfahren durchzuführen, ab, soweit sie darauf eintrat. Das Bau- und Justizdepartement des Kantons Solothurn hiess am 29. Juni 2010 die Beschwerde des VCS gegen diesen Entscheid gut; es hob den Entscheid der Baukommission vom 12. November 2009 und die am 17. Mai 2004 erteilte Baubewilligung für die Umnutzung des Melitta-Gebäudes auf. Die dagegen erhobene Beschwerde der Genossenschaft Migros Aare wies das Verwaltungsgericht des Kantons Solothurn am 7. Februar 2012 ab.
B. Die Genossenschaft Migros Aare beantragt dem Bundesgericht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, die erwähnten Entscheide des Verwaltungsgerichts sowie des Bau- und Justizdepartements aufzuheben und die Verfügung der Baukommission vom 12. November 2009 zu bestätigen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Der VCS, das Bau- und Justizdepartement und das Verwaltungsgericht ersuchen um Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Umwelt hat sich zur Beschwerde geäussert, ohne einen Antrag zu stellen. Die Beschwerdeführerin und der VCS halten in weiteren Eingaben an ihren Anträgen fest.
Der Präsident der I. öffentlich-rechtlichen Abteilung hat der Beschwerde am 13. April 2012 mit Ausnahme des Parteientschädigungspunkts die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Der angefochtene Entscheid bestätigt die Verfügung des Bau- und Justizdepartements, welche die am 17. Mai 2004 erteilte Baubewilligung für die Umnutzung des Melitta-Gebäudes aufhebt und die Gemeinde Egerkingen dazu anhält, über das seinerzeit eingereichte Baugesuch neu zu befinden. Da das Urteil des Verwaltungsgerichts das Verfahren nicht abschliesst, handelt es sich um einen Zwischenentscheid, der beim Bundesgericht lediglich anfechtbar ist, wenn die Voraussetzungen von <ref-law> erfüllt sind. Gemäss lit. b der genannten Bestimmung kann gegen Zwischenentscheide Beschwerde geführt werden, wenn die Gutheissung des Rechtsmittels sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde. Eine solche Situation ist hier gegeben. Wird die Beschwerde gutgeheissen, so ist die Baubewilligung vom 17. Mai 2004 rechtskräftig, und es erübrigt sich nicht nur, eine Umweltverträglichkeitsprüfung, sondern auch ein Gestaltungsplanverfahren durchzuführen.
Die übrigen Sachurteilsvoraussetzungen sind ebenfalls erfüllt. Auf die Beschwerde ist daher einzutreten. Anders verhält es sich nur bezüglich des Antrags, auch den Entscheid des Bau- und Justizdepartements vom 29. Juni 2010 aufzuheben, da dieser wegen des Devolutiveffekts ohnehin als mitangefochten gilt.
2. 2.1 Streitgegenstand bildet die Rechtsbeständigkeit der Baubewilligung, welche die Gemeinde am 17. Mai 2004 für die Umnutzung des Melitta-Gebäudes erteilt hat. Die Vorinstanz gelangt zum Schluss, dass diese Bewilligung mangels korrekter Eröffnung gegenüber dem VCS nicht rechtskräftig geworden sei, sie zudem an einem Mangel leide und deshalb aufgehoben werden müsse.
Ausschlaggebend für dieses Ergebnis ist nach Auffassung der Vorinstanz, dass für die fragliche Umnutzung eine UVP erforderlich sei. Damit komme dem VCS nach <ref-law> (SR 814.01) grundsätzlich das Beschwerderecht zu. Die nach <ref-law> in einem solchen Fall vorgeschriebene Mitteilung des Baugesuchs bzw. der Baubewilligung an den VCS sei nicht erfolgt. Dieser habe von der Umnutzung deshalb keine Kenntnis gehabt und auch nicht haben müssen. Seine Eingabe vom 8. Mai 2007 müsse daher noch als rechtzeitige Beschwerde anerkannt werden. Diese sei zudem begründet, da keine UVP durchgeführt worden sei. Aus diesem Grund habe das Bau- und Justizdepartement die Baubewilligung zu Recht aufgehoben und die Sache zur Neubeurteilung an die Gemeinde Egerkingen zurückgewiesen.
Demgegenüber erachtet die Beschwerdeführerin die am 17. Mai 2004 erteilte Umnutzungsbewilligung als rechtskräftig. Sie kritisiert die Argumentation im angefochtenen Entscheid in zwei Punkten. Einerseits rügt sie eine unvollständige Sachverhaltsfeststellung durch die Vorinstanz. Diese habe ausser Acht gelassen, dass die für die Umnutzung verlangte UVP bereits in einem früheren Zeitpunkt - im Rahmen einer grösser angelegten UVP für das gesamte Gebiet - durchgeführt worden sei. Eine erneute UVP sei unter diesen Umständen nicht erforderlich. Anderseits bestreitet die Beschwerdeführerin, dass das Rechtsmittel des VCS rechtzeitig erhoben worden sei. Es treffe zwar zu, dass die vorgeschriebene Eröffnung nicht erfolgt sei, doch habe der VCS bereits lange Zeit vor der Eingabe vom 8. Mai 2007 Kenntnis von der Umnutzung des Melitta-Gebäudes gehabt und hätte daher viel früher reagieren müssen.
2.2 Rechtsmittel gegen Baubewilligungen sind im Kanton Solothurn innert 10 Tagen seit der Zustellung des Entscheids zu erheben. Für das Verfahren ist das Gesetz vom 15. November 1970 über den Rechtsschutz in Verwaltungssachen (Verwaltungsrechtspflegegesetz; BGS 124.11) massgebend (§ 2 Abs. 6 der kantonalen Bauverordnung vom 3. Juli 1978 [BGS 711.61]). Nach § 19 Abs. 2 des Verwaltungsrechtspflegegesetzes sind Entscheide als solche zu bezeichnen und im vorgeschriebenen Verfahren zu eröffnen. Es ist unbestritten, dass das Gesuch für die Umnutzung des Melitta-Gebäudes nicht in der vorgeschriebenen Form veröffentlicht und die erteilte Baubewilligung vom 17. Mai 2004 dem VCS nicht zugestellt worden ist. Das kantonale Recht regelt nicht, wie in einem solchen Fall unterbliebener Eröffnung der Beginn der Rechtsmittelfrist zu bestimmen ist. Die Vorinstanz erklärt dazu lediglich, es könne dem VCS kein Vorwurf gemacht werden, dass er die Baubewilligung erst rund drei Jahre nach deren Erteilung angefochten habe; das erst dann erhobene Rechtsmittel müsse deshalb als rechtzeitig anerkannt werden.
2.3 Das Bundesgericht erklärt in seiner bisherigen Rechtsprechung, dass für Dritte, die zu Unrecht nicht in ein Baubewilligungsverfahren einbezogen werden, die Rechtsmittelfrist erst mit der tatsächlichen Kenntnisnahme des Entscheids zu laufen beginnt. Aus Gründen der Rechtssicherheit und nach dem Grundsatz von Treu und Glauben, der Behörden wie Privaten gleichermassen rechtsmissbräuchliches Verhalten verbietet (<ref-law>), darf der Dritte aber den Beginn des Fristenlaufs nicht beliebig hinauszögern, sobald er auf irgendeine Weise Kenntnis von der ihn berührenden Entscheidung erhalten hat. Er hat sich vielmehr danach zu erkundigen, wenn Anzeichen dafür vorliegen, und rechtzeitig zu reagieren (<ref-ruling> E. 4.2 S. 312 f. mit Hinweisen). Die Rechtsprechung hebt auch hervor, dass es nicht angeht, Verfügungen, die dazu bestimmt sind, Rechtskraftwirkungen zu entfalten, noch nach beliebig langer Zeit in Frage zu stellen. Umgekehrt ist der Grundsatz zu beachten, dass der Verfügungsadressat aus einer unterbliebenen oder fehlerhaften Eröffnung keine Nachteile erleiden soll. Wann die Rechtsmittelfrist zu laufen beginnt, ist nach dem Grundsatz von Treu und Glauben im Einzelfall zu bestimmen. Als Leitlinie gilt dabei, dass derjenige, der aus einer nicht offiziellen Quelle Kenntnis von einem ihn berührenden Entscheid erlangt, zwar nicht innert Frist seit dieser Kenntnisnahme ein Rechtsmittel ergreifen muss. Allerdings darf er in diesem Fall auch nicht einfach untätig bleiben, sondern hat die je nach den Umständen gebotenen Schritte zu unternehmen (<ref-ruling> E. 3 S. 94). Dabei tritt mit der Zeit das Rechtsschutzinteresse gegenüber jenem der Rechtssicherheit in den Hintergrund. Welcher der beiden Gesichtspunkte den Vorrang verdient, ist aufgrund einer Interessenabwägung zu beurteilen (Urteil P.883/1983 vom 14. März 1984 E. 3, in: ZBl 85/1984 S. 425; vgl. auch ANDRÉ GRISEL, Traité de droit administratif, 1984, S. 875).
In seiner bisherigen Praxis anerkannte das Bundesgericht das Rechtsmittel eines Nachbarn, dem eine Baubewilligung zu Unrecht nicht zugestellt worden war und der wenige Monate danach bei Baubeginn noch gleichentags reagiert hatte, als rechtzeitig (Urteil P.883/1983 vom 14. März 1984 E. 4, in: ZBl 85/1984 S. 425). Anders beurteilte es dagegen das Rechtsmittel eines Nachbarn, der erst vier Jahre nach der Erstreckung einer befristeten Bewilligung dagegen Beschwerde erhob, obwohl er Anhaltspunkte dafür haben musste, dass diese verlängert worden war und er deshalb gehalten war, sich bei der Gemeindeverwaltung zu erkundigen (<ref-ruling> E. 4a S. 77). Ebenfalls nicht mehr als rechtzeitig erachtete das Bundesgericht eine Beschwerde des Rheinaubunds, der trotz einer negativen Stellungnahme der kantonalen Behörden nicht sofort reagierte (Urteil 1A.256/1993 vom 31. Dezember 1993 E. 2b, in: ZBl 95/1994 S. 529). In zwei neueren Fällen, auf die sich die kantonalen Instanzen beziehen, bejahten die kantonalen Instanzen die Rechtzeitigkeit einer nachträglichen Beschwerde des VCS, dem Baubewilligungen zu Unrecht nicht eröffnet worden waren. Das Bundesgericht schützte diese Beurteilung, da nicht feststand, dass der VCS früher hätte reagieren können (Urteile 1A.136/2004 vom 5. November 2004 E. 3.2.2 mit Hinweisen, in: URP 2005 S. 1; 1A.33/2007 vom 22. Oktober 2007 E. 6.4).
Im Lichte dieser Rechtsprechung ist zu prüfen, ob die Vorinstanz die Eingabe des VCS vom 8. Mai 2007 noch als rechtzeitig ansehen durfte. Da es dabei um die Konkretisierung des verfassungsrechtlichen Grundsatzes von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV) geht, kommt dem Bundesgericht dabei freie Kognition zu.
2.4 Die Vorinstanz erklärt, die Umnutzung des Melitta-Gebäudes sei von aussen nicht ohne weiteres erkennbar. Der VCS sei deshalb nicht verpflichtet gewesen, Nachforschungen über die Einhaltung der Publikationspflicht durch die Behörden zu treiben. Der Beschwerdeführer beruft sich demgegenüber auf mehrere Umstände, die belegten, dass der VCS bereits lange Zeit vor der Eingabe vom 8. Mai 2007 von der Umnutzung wusste. Da diese Hinweise nach der erwähnten Rechtsprechung für die Beurteilung der Frage, ob der VCS nach Treu und Glauben rechtzeitig reagiert hat, rechtserheblich sein können, hätte die Vorinstanz dazu die erforderlichen Sachverhaltsfeststellungen treffen müssen. Das Bundesgericht kann die fehlenden Feststellungen indessen nachfolgend selber treffen, da die tatsächlichen Behauptungen der Beschwerdeführerin aus den Akten hervorgehen und vom VCS nicht bestritten werden (vgl. <ref-law>).
Wie aus dem angefochtenen Entscheid hervorgeht, erhöhte die Umnutzung des Melitta-Gebäudes die Verkaufsfläche um 3'800 m2 und damit um mehr als 10 %. Zudem wurden 80 neue Parkplätze geschaffen. Mit der Umnutzung entstand - wie der VCS selber ausführt - ein neuer Komplex des Einkaufszentrums, der auch als Gäu-Park West bezeichnet wird. Auch wenn der Gäu-Park heute aus mehreren Teilen besteht und deshalb unübersichtlich erscheint, ist die Umnutzung des Melitta-Gebäudes angesichts der Veränderungen der Gebäudehülle - insbesondere der neu geschaffenen Verbindung mit dem Gäu-Park Süd - doch von aussen her ohne weiteres zu erkennen. Die gegenteilige Würdigung der Gegebenheiten im angefochtenen Entscheid vermag nicht zu überzeugen.
Der VCS vermochte sich aufgrund des äusseren Eindrucks allerdings noch kein Bild über das genaue Ausmass der im Gebäudeinneren erfolgten Veränderungen, insbesondere über die Zahl neu geschaffener Parkplätze und die UVP-Pflicht, verschaffen. Zu prüfen ist nach der erwähnten Rechtsprechung, ob der VCS nicht gehalten war, über den erfolgten Umbau bei der Gemeinde weitere Erkundigungen einzuholen, um gestützt auf diese allenfalls von seinem Beschwerderecht Gebrauch zu machen.
2.5 Der VCS war mit den Verhältnissen des Gäu-Parks vertraut, hatte er doch bereits bei früheren Bauetappen Einsprache erhoben. Am 23. April 2003 schloss er mit der Gäu-Park AG eine Vereinbarung. Diese betraf den Gäu-Park 2, also jenen Komplex, der mit dem Melitta-Gebäude verbunden wurde. In dieser Vereinbarung wird insbesondere die Parkraumbewirtschaftung des Gäu-Parks 2 detailliert geregelt. Vertreter des VCS kontrollieren deren Umsetzung. Zu diesem Zweck besuchte im März 2005, also nach der Einweihung des neuen Non Food-Bereichs im ehemaligen Melitta-Gebäude, die Geschäftsführerin des VCS Solothurn den Gäu-Park 2.
Anlässlich dieses Besuchs erhielt sie zwar nicht Kenntnis von der Baubewilligung zur Umnutzung des Melitta-Gebäudes. Doch bestanden damals mehrere Anhaltspunkte, die auf die erfolgte Umnutzung hindeuteten. Wie bereits erwähnt, tritt diese äusserlich durch die neu geschaffene Verbindung zwischen dem Gäu-Park Süd zum neu geschaffenen Non Food-Komplex im Melitta-Gebäude in Erscheinung. Die Geschäftsführerin des VCS Solothurn befasste sich bei ihrem Besuch mit der Nutzweise des Gäu-Parks Süd und beanstandete, dass dort entgegen der getroffenen Vereinbarung nicht nur Non Food-Geschäfte angesiedelt seien; ausserdem überprüfte sie die Parkplatzbewirtschaftung. Das Nutzungskonzept und die Parkplatzbewirtschaftung haben aber mit der Inbetriebnahme des Melitta-Gebäudes Änderungen erfahren, die bei der vorgenommenen Besichtigung der Verhältnisse nicht verborgen bleiben konnten. Hinzuweisen ist in diesem Zusammenhang insbesondere auch auf die Erweiterung der Einstellhalle des Gäu-Parks 2 um 46 Parkplätze im Zusammenhang mit der Umnutzung des Melitta-Gebäudes. Wohl mag es zutreffen, dass sich der VCS aufgrund der erwähnten Besichtigung kein genaues Bild vom Ausmass der Umnutzung verschaffen konnte. Er hatte aber nach der Rechtsprechung hinreichende Anhaltspunkte, um bei der Gemeinde die nötigen näheren Aufschlüsse darüber einzuholen.
Der VCS wäre deshalb nach dem Besuch der Geschäftsführerin nach Treu und Glauben gehalten gewesen, die nötigen Schritte zu unternehmen, um Beschwerde gegen die Umnutzung des Melitta-Gebäudes erheben zu können. Dies gilt umso mehr, als die Umnutzung in diesem Zeitpunkt bereits vollzogen war und beachtliche Ausmasse aufwies, so dass sich mit Blick auf die Rechtssicherheit eine sofortige Ausübung des Beschwerderechts aufdrängte.
In dieser Hinsicht unterscheidet sich der hier zu beurteilende Sachverhalt von jenem der zwei Entscheide, auf die sich die kantonalen Behörden beziehen. So hatte der VCS im einen Fall gegen die fehlerhaft ausgeschriebene Bewilligung für die Erweiterung eines Möbelmarkts sofort nach der Einweihung des Erweiterungsbaus Beschwerde erhoben (Urteil 1A.136/2004 vom 5. November 2004, in: URP 2005 S. 1). Im anderen bestanden keine genügenden Anhaltspunkte, dass der VCS bereits vor der Erhebung des Rechtsmittels Kenntnis vom damals umstrittenen Ausbau einer Lagerhalle Kenntnis erlangt hatte (Urteil 1A.33/2007 vom 22. Oktober 2007 E. 6.4).
Unter den dargestellten Umständen ist die Beschwerdeerhebung durch den VCS nicht rechtzeitig erfolgt. Der anders lautende Entscheid der Vorinstanz läuft dem Grundsatz von Treu und Glauben zuwider und verletzt damit Bundesrecht.
3. Aus diesen Gründen ist die Beschwerde gutzuheissen, soweit darauf einzutreten ist, und der angefochtene Entscheid aufzuheben. Zugleich sind die Verfügung der Baukommission Egerkingen vom 12. November 2009 und - im Sinne der Klarheit - auch die Baubewilligung vom 17. Mai 2004 für die Umnutzung der bestehenden Werkhalle Melitta und die Einstellhallenerweiterung auf GB Egerkingen Nrn. 946 und 1913 zu bestätigen.
Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem VCS aufzuerlegen (<ref-law> und <ref-law>). Er hat ausserdem die Beschwerdeführerin für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Zur Neufestsetzung der Kosten und Entschädigungen des kantonalen Verfahrens wird die Sache an die Vorinstanz zurückgewiesen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und der angefochtene Entscheid des Verwaltungsgerichts des Kantons Solothurn vom 7. Februar 2012 aufgehoben.
Die Verfügung der Baukommission Egerkingen vom 12. November 2009 und die Baubewilligung vom 17. Mai 2004 für die Umnutzung der bestehenden Werkhalle Melitta und die Einstellhallenerweiterung auf GB Egerkingen Nrn. 946 und 1913 werden bestätigt.
2. Zur Neufestsetzung der Kosten und Entschädigungen des kantonalen Verfahrens wird die Sache an die Vorinstanz zurückgewiesen.
3. Die Gerichtskosten von Fr. 4'000.-- werden dem VCS auferlegt.
4. Der VCS hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien, der Baukommission der Einwohnergemeinde Egerkingen, dem Bau- und Justizdepartement sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 6. März 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Aemisegger
Der Gerichtsschreiber: Dold