Zagrała także siostrę Leonię w obrazie Prymas Teresy Kotlarczyk (2000) opowiadającym o latach uwięzienia Stefana Wyszyńskiego. Jako donosząca na prymasa zakonnica ukazała uwikłanie swej bohaterki w ludzkie słabości.
Te dwie filmowe role zapewniły Ostaszewskiej kolejny triumf w Gdyni – po raz kolejny nagrodzona została za najlepszą pierwszoplanową rolę żeńską. Za rok 2000 została też wyróżniona Paszportem Polityki w kategorii Film.
Ostaszewska imponuje precyzją i dojrzałością myślenia o zawodzie aktorskim. W wywiadzie dla magazynu „Pani” (5/2000) mówiła:
Jest taki moment w konstruowaniu postaci, gdy pozwalam jej niejako wniknąć w moje życie. To czas, gdy chcę poczuć, jak ta postać się porusza, co lubi jeść, jakiej muzyki słucha. Muszę być tą postacią. Bardzo dużo o niej myślę, w domu piszę monologi wewnętrzne. Żyję nią przez dwadzieścia cztery godziny na dobę. Kiedy wreszcie ją „uchwycę”– wracam do niej już tylko wtedy, gdy gram.
Jacek Tabęcki pisał o Ostaszewskiej w ,,Filmie”:
Maja Ostaszewska wciela się w swoje bohaterki bez reszty (...). Młode kobiety, które gra (którymi jest? których życiem żyje?), są niewygodne do oglądania – uwierają, irytują, sprawiają ból albo przykrość. Nie można zwyczajnie gapić się na nie, wnikają w widza, nie sposób się od nich opędzić. (...) Są niewygodne jak każda osoba osamotniona wewnętrznie, ale potrzebująca dopełnienia psychicznego i fizycznego przez drugą osobę – mężczyznę, kobietę, dziecko. I stale przypominają, że za wszystko trzeba płacić (...). Bo cokolwiek by człowiek zrobił, i tak oczekiwania bohaterek Ostaszewskiej, choć zwyczajne, są jednocześnie zbyt wielkie.
W 2002 roku Ostaszewska zagrała Sonię w Płatonowie Pawła Miśkiewicza (Teatr Dramatyczny w Warszawie). Kolejne role stworzyła na deskach TR Warszawa. Wcieliła się w postać Klary w Stosunkach Klary Dei Loher, spektaklu w reżyserii Krystiana Lupy (2003). Sportretowała młodą, zagubioną w świecie dziewczynę poszukującą tożsamości i własnej drogi. Iza Natasza Czapska pisała w „Życiu Warszawy” (07.04.2003):
„Stosunki Klary” to przede wszystkim kolejna kreacja Mai Ostaszewskiej. Nie da się zapomnieć podskórnego dygotu Klary, wewnętrznego krzyku, z jakim zmaga się w kontakcie z innymi ludźmi, z przerastającymi ją problemami, ze światem zewnętrznym. W jej ciemnym, wilgotnym, hardym spojrzeniu znać ogromną siłę i prawdę, z jaką porusza się w obcej jej rzeczywistości Klara. I przejmujący strach.
U Grzegorza Jarzyny zagrała Elwirę w Giovannim wg Mozarta i Moliera (2006). Później zajęła się przede wszystkim współpracą z Krzysztofem Warlikowskim, od początku jest częścią zespołu tworzonego przez niego Nowego Teatru. W swoich dwóch pierwszych rolach u tego reżysera zagrała kobiety niestabilne emocjonalnie – była Trudą w Krumie Hanocha Levina (2005, koprodukcja z Narodowym Starym Teatrem w Krakowie) i Harper Amaty Pitt w Aniołach w Ameryce Tony'ego Kushnera (2007). O Harper Amaty Pitt Ostaszewska mówiła w wywiadzie dla stołecznej „Gazety Wyborczej” (2007/41):
Jest uzależniona nie tylko od valium, ale także od swojego partnera i własnej depresji. Ważne było dla nas pokazanie tego uwikłania, że patologię tego związku tworzą oboje. Harper podświadomie od dawna czuła, że jej mąż jest gejem, a jednak się z nim związała. Pokazujemy tu też bolesny proces jej dojrzewania, najpierw do prawdy, do szczerości, potem do zbudowania samej siebie. (...) Harper pogrąża się w bólu, żeby oczyszczona dotrzeć do swojego wewnętrznego światła. To sztuka o wybaczaniu.
Za rolę Harper aktorka została uhonorowana Nagrodą im. Aleksandra Zelwerowicza.
Zagrała we wszystkich kolejnych spektaklach Warlikowskiego: w 2009 roku w (A)polonii – pierwszej realizacji przygotowanej przez Warlikowskiego w Nowym Teatrze, a zarazem pierwszym polskim przedstawieniu, które pokazane zostało na głównej scenie Festiwalu Awiniońskiego. W 2010 roku Ostaszewska grała w Końcu, w 2011 roku w Opowieściach afrykańskich według Szekspira, w 2013 roku w Kabarecie Warszawskim, w 2015 roku we Francuzach zrealizowanych na podstawie prozy Marcela Prousta. W 2018 roku świetną rolę stworzyła w Wyjeżdżamy na podstawie Hanocha Levina.
Na srebrnym ekranie wystąpiła m.in. w Przemianach Łukasza Barczyka (2003), za którą to rolę otrzymała nominację do Orła. W filmie o zachwianych i zakłamanych rodzinnych relacjach wcieliła się w postać Marty, kobiety uwikłanej w nieudane małżeństwo, rodzące się nowe uczucie, stającej w obliczu tragedii – śmierci siostry. Zagrała też Annę – jedną z głównych ról w Katyniu Andrzeja Wajdy (2007).
W 2014 roku zagrała żonę głównego bohatera w filmowej biografii Ryszarda Kuklińskiego – Jack Strong Władysława Pasikowskiego. Za tę rolę otrzymała nagrodę Orła za pierwszoplanową rolę kobiecą. Sukces ten powtórzyła rok później: w nagrodzonym w Berlinie filmie Małgorzaty Szumowskiej Body / Ciało (2015) jako psychoterapeutka i spirytystka dała prawdziwy popis aktorskiego kunsztu.
W 2019 roku oglądać można ją było w (Nie)znajomych w reżyserii Tadeusza Śliwy i Ja teraz kłamię Pawła Borowskiego. Z kolei u Szumowskiej pojawiła się ponownie w krótkim, zrealizowanym dla modowej marki Miu Miu klipie Nightwalk (2019), a także w jednej z głównych ról w filmie Śniegu już nigdy nie będzie (2020).
Po wielu znaczących rolach dramatycznych Ostaszewska zaskoczyła widzów talentem komediowym: w serialu Przepis na życie (2011-2013), wraz z Piotrem Adamczykiem skradła show bohaterom pierwszego planu, status kultowych zyskały też jej występy w komercyjnych przebojach Pitbull. Nowe początki i Pitbull. Niebezpieczne kobiety Patryka Vegi (2016). Zagrała też jedną z głównych ról w trzech częściach filmu Teściowie (2021, 2023, 2025) w reżyserii Jakuba Michalczuka, które biły rekordy frekwencji w kinach.
W ostatnich latach można ją było zobaczyć także w głośnych dramatach, takich jak Magnezja (2020) w reżyserii Macieja Bochniaka, Broad Peak (2022) Leszka Dawida, Zielona granica (2023) Agnieszki Holland, Kolory zła: Czerwień (2024) Adriana Panka.
Ważnym punktem jej filmografii była rola w filmie Śniegu już nigdy nie będzie (2021) Małgorzaty Szumowskiej i Michała Englerta. To tragikomedia, której głównym bohaterem jest przybyły z Ukrainy masażysta, który staje się powiernikiem grupy bogaczy zamieszkujących zamknięte osiedle. Krytycy podkreślali rewelacyjną grę Ostaszewskiej.
Aktorka zagrała także matkę Fryderyka Chopina w głośnej produkcji Michała Kwiecińskiego Chopin, Chopin! (2025).
Ostaszewska nie stroni także od seriali, wzięła udział między innymi w popularnej Diagnozie emitowanej w TVN w latach 2017–2019 w reżyserii m.in. Xawerego Żuławskiego, pojawiła się także gościnnie w kilku odcinkach Office.pl
Równie intensywnie rozwija się teatralna kariera aktorki. Ostatnie lata przyniosły przede wszystkim jej kolejne role w spektaklach Krzysztofa Warlikowskiego w Nowym Teatrze w Warszawie.
W 2021 roku premierę miała Odyseja. Historia dla Hollywoodu, w której aktorka zagrała rolę Izoldy Ragensberg. Warlikowski sięgnął tutaj po dzieła Hanny Krall, by w nich odnajdywać antyczne toposy:
„Odys wraca z wojny trojańskiej, moja bohaterka Izolda Regensberg – postać autentyczna, opisana przez Hannę Krall – przeżyła II wojnę światową i Holocaust. Jest Żydówką, która ukrywa się, farbuje włosy na blond i udaje Polkę. Jej podróż to tak naprawdę podróż do ukochanego. Do męża. To, czego dokonuje, jej niezwykłe losy, odwaga, heroizm są na miarę antycznych tragedii. Udało jej się uciec z getta, pomóc części swojej rodziny. Torturowana przyznała się do tego, że jest Żydówką, trafiła do Auschwitz, ponieważ miała założoną kartotekę, unika selekcji, następnie jedzie do obozu w Guben, skąd ucieka... A to dopiero początek jej drogi” – mówiła aktorka w rozmowie z Dorotą Wyżyńską na łamach „Gazety Wyborczej.
Kolejną głośną sztuką Krzysztofa Warlikowskiego z udziałem Ostaszewskiej była Elizabeth Costello według tekstów Johna Maxwella Coetzeego. Centralnym tematem tej sztuki jest stosunek ludzi do zwierząt, co wiąże się ściśle z osobistymi poglądami aktorki,znanej obrończyni praw zwierząt.
Na początku 2026 r. premierę miała Europa w reżyserii Warlikowskiego. Spektakl, oparty na tekście Wajdiego Mouawada, stawia pytania o źródła przemocy i banalność zła.
Ale Ostaszewska gra nie tylko u Warlikowskiego. W 2025 miała miejsce premiera spektaklu Kofman. Podwójne wiązanie Janusza Margańskiego i Moniki Muskały w reżyserii Katarzyny Kalwat, będącego koprodukcją Nowego Teatru i Festiwalu Nowe Epifanie w Warszawie. Główna bohaterka sztuki to Sarah Kofman, pochodząca z żydowskiej rodziny francuska filozofka, która w czasie swojego wojennego dzieciństwa była ukrywana przez Francuzkę. Konflikt między dwoma matkami – rodzoną i przybraną – stanowi oś dramatyczną spektaklu. „Kofman. Podwójne wiązanie to niezwykły popis Mai Ostaszewskiej, która gra tu tak, że mam ciarki, a czasem i łzy w oczach” – pisała Wiktoria Tabak w „Gazecie Wyborczej”.
Maja Ostaszewska jest aktywną uczestniczką życia publicznego: walczy, między innymi, o prawa kobiet i zwierząt. W 2019 roku zaangażowała się na przykład w kampanię prozwierzęcej organizacji Otwarte Klatki, której celem był sprzeciw wobec hodowli zwierząt na futra. W wywiadzie dla "Gazety Wyborczej" mówiła:
Mam to szczęście, że szacunku do przyrody uczyli mnie rodzice, wychowywali mnie w domu pełnym zwierząt, w którym właśnie z powodów etycznych nie jadło się mięsa. (...) Jestem szczerze dumna z tego, że udało mi się przekonać wiele osób do przejścia na dietę roślinną, do zrezygnowania z noszenia futer i obszyć futrzanych, do bojkotowania cyrków wykorzystujących zwierzęta. Swoją działalność na rzecz praw zwierząt traktuję na równi z działalnością artystyczną albo poważniej.
Za działalność społeczną została w 2017 roku uhonorowana Nagrodą im. Teresy Torańskiej. W tym samym roku uhonorowano Ostaszewską także nagrodą Fundacji Izabeli Jarugi-Nowackiej „Okulary Równości” w kategorii Prawa kobiet i zwalczanie dyskryminacji z powodu płci za „konsekwentne wspieranie wszystkich akcji na rzecz praw kobiet, aktywne zbieranie podpisów pod obywatelskim projektem <Ratujmy kobiety>, odwagę sprzeciwiania się pogardzie i nienawiści”
Za działalność społeczną aktorka otrzymała także nagrodę im. Teresy Torańskiej przyznawana przez redakcję „Newsweeka”.
