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).
W ostatnich latach Ostaszewska zaskoczyła także 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).
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.
