But after a strong start with 2000's Music, her fortunes began to wane in the US, where she's managed to reach the top ten just six times in the past fifteen years.
There were all kinds of factors at play. The pulling of the American Life video, and the cool reception of the album harmed her brand. A new generation of acts less than half her age had also come along and usurped her, but the more worrying aspect of her music career was the inconsistency it seemed to have been marked by in this third decade.
Where Ray of Light succeeded because it sounded like an hour long series of meditations - each song working itself up into a frenzy and towards a climax - Music didn't have the patience to go through all of that navel gazing for the journey alone.
More often than not, Music was at its best when it attempted to push things forward as it did with nearly all of the Mirwais numbers. It chopped and changed, moving from complete electronica to stripped back acoustic guitar, often in the middle of a song.
When things got jarring, things also got interesting - and the push and pull of the Mirwais songs: full of stops and starts and stuttering effects and vocals - was never more hypnotic than on Paradise (Not For Me).
It's here that the blunt, stripped back girl of old gets a re-tune - mid song -and we are made the better for it. The chopping synths, the effects, the direct and indirect lyrics. This time around, M is the blunt girl who has come out the other side - like an electronic version of the geisha M is so obsessed by. This one just happens to sound like she's stuck somewhere behind a fake xylophone at an open-mic poetry night in Paris. Yes that combination is as amazing as it sounds.
American Life was perhaps the first M album to receive a hostile reception from critics and the public alike.
It was also the flag bearer for the new reality for M in a changing pop scene. On AL the raw, vital M finally gets another shot at a full album, but the perception is that her vitality is lost somewhere along the very long road from the inception of the album to its release.
The result? A batch of songs that often only found their stride when they were remixed or reworked (on the Remixed and Revisited EP or the Reinvention tour).
The three Rs improved on a lot of the tracks even if Nothing Fails, Hollywood and Love Profusion were already great additions to the cannon.
But the standout on AL was another piece that needed no cosmetic work. The wonky pop of Mother and Father has to be one of M's most interesting songs ever. Those old faithful themes
of mum and dad were reincarnated brilliantly - and the result is one of the most subversive moments of M's long recorded career.
With Confessions On A Dance Floor she delivered again, sparking her third coming and perhaps one of her most celebrated musical turns ever in her 30 plus years.
Stuart Price's wall of sound, and what has probably been the most consistently brilliant album of her career, makes the choice for best non single a tough one.
Forbidden Love, a kind of 00s La Isla Bonita has to be a contender, as do the rather bonkers Future Lovers ('let's forget your life, your problems, administration, bills and loans') and Isaac. But my money is on Push - it's like the musical wrestling match. A push, drag and pull kind of routine, which one must assume must've been inspired by martial arts loving Guy Ritchie.
When we know we can expect more from someone, we're more likely to forgive them for their indiscretions.
On Hard Candy there are more than a few mistakes that M needs to atone for. Spanish Lesson has to be one of the worst sins M has committed in her entire career - as was her hitching a ride on the Timberlake/Timbaland/Pharrell bandwagon without adding enough of her own touch. Those hit makers made better stuff with Nelly Furtado and Justin than they did with her.
But for its failings HC atones with at least a half a dozen strong numbers - Give It 2 Me being among one of her best late period singles, though that's not saying much - and the trilogy of She's Not Me/Devil/Voices each have so much going for them that I'm gonna abstain and vote for Heartbeat instead as best non album track, because, well, it's the old Into The Groove M moment of the album.
But instead, it was largely an inconsistent covering of all bases, and worse still, an example of M spending yet more time chasing the bandwagon rather making her own way forward.
Once upon a time, we used to ricochet between the good girl and the bad girl, but by this stage, (especially with MDNA) M fans often have to settle for being shuttled between a hit chaser and, paradoxically, a woman, who, when she abandons interest in sounding current, is in a class of her own.
The problem is partly down to editing. Because MDNA had some great songs on it. But for every Gang Bang or Love Spent you had to contend with a Some Girls or Superstar.
American Life would've worked better if it had been re-tooled but on MDNA, the problem is in the inconsistency. It's a major issue because there's so much B grade material on the main album, that to salvage it, you have to break into the bonus deluxe edition tracks to make up for the short fall. MDNA should've been another William Orbit package - it's where she most frequently was at her best, even if stompers like I'm Addicted and I Don't Give A were great new songs.
Again, despite the disasters of leaks, Drake dramas, ageism and no airplay, the central problem to an album like Rebel Heart is it's inconsistency.
This is the first album in M's career that has accounted for over 20 songs. But much like MDNA and Hard Candy for every decent, brilliant song added to the cannon, there's at least another shocker on offer.
This time around, the singles have been better choices, and depending on your taste of M's styles there's an album track to your taste just waiting for you. The title track? Gorgeous, human sounding pop. Prefer your Madonna music to be more cinematic? Try Messiah it's the sound of someone who has no peer when it comes to pop music. Like the Drowned World style Madge? Well there's Wash All Over Me.
Personally, my pick of the bunch is HeartBreakCity. It's a little jarring, and it's the stripped back studio girl that I love so much. Had the album been culled down to 12 or 13 tracks of the calibre of these tracks, Rebel Heart could've been up there with M's best ever albums.