In 2003, Madonna planned to release a special commemorative box set to celebrate her twentieth anniversary in the music business and the release of her first studio album, Madonna, in 1983. The plan for the box set was eventually cancelled and Remixed & Revisited was conceived in its place. The compilation contains remixed versions of four songs from American Life and a previously unreleased song called "Your Honesty"; co-written and co-produced by Dallas Austin, the track is from Madonna's sixth studio album Bedtime Stories era (1994). "Nobody Knows Me" was remixed by performance artist Mount Sims, Headcleanr mixed "American Life" and "Love Profusion". DJ Jason Nevins remixed "Nothing Fails", while "Into the Hollywood Groove" was created by The Passengerz. On December 9, 2003, Warner Music France released a box set version containing both the remix collection and the original album American Life in a cardboard sleeve entitled Édition Spéciale 2CDs: American Life + Remixed & Revisited.
The medley track "Like a Virgin/Hollywood" was performed during the opening of the 2003 MTV Video Music Awards on August 27, 2003, where Madonna was joined by Britney Spears, Christina Aguilera, and Missy Elliott. The performance started with Spears appearing on stage on top of a giant wedding cake while wearing a wedding gown and veil; she sang the first few lines of "Like a Virgin" before Aguilera appeared from behind the cake and joined her. Madonna then emerged from the cake wearing a black coat and a hat and started singing "Hollywood" before proceeding to kiss Spears and Aguilera on the lips. Missy Elliott came out from a wedding chapel to sing her song "Work It" halfway through the performance. The kiss generated strong reaction from the media. Feminist author Camille Paglia described the moment as great; she noted that the kiss was like Madonna saying to Spears, "I'm passing the torch to you." However, according to her, Spears could not take advantage of the kiss as later her career and lifestyle came under immense media scrutiny and criticism. Paglia said that "literally from that kiss, from that moment onward, Britney has spiraled out of control. It’s like Madonna gave her the kiss of death!" Madonna commented on the kiss; "I am the mommy pop star and she is the baby pop star. And I am kissing her to pass my energy on to her." This performance was listed by Blender magazine as one of the twenty-five sexiest music moments on television history.MTV listed the performance as the number-one opening moments in the history of MTV Video Music Awards.
In the United States, Remixed & Revisited debuted at number 115 on the Billboard 200, selling 22,000 copies in its first week. It also debuted and peaked at number 128 on the Top Comprehensive Albums chart. According to Nielsen SoundScan, the EP has sold 114,000 copies as of August 2005 in the United States. The Nevins' mix of "Nothing Fails" charted on the Canadian Singles Chart at seven and topped the Hot Dance Club Play chart. It also debuted on the album charts of Belgium, in Flanders and Wallonia, and Switzerland. The album charted in Italy as a song, reaching a peak of number two. It also charted in Finland and Denmark as an EP on the singles charts.
Stephen Thomas Erlewine of Allmusic felt that the presence of a "strong hook and a strong sense of fun" was missing from the compilation, except for the song "Your Honesty", which he declared as the best track despite feeling its beats to be a little outdated. He compared the work of the remixers as "as subtle as a jackhammer, whether it's on the metallic-flaked "American Life" by Headcleanr or the '90s-retro Nevins mix of "Nothing Fails". On all these mixes, Madonna sounds as if she's out of step with the music of 2003". Erlewine also compared Spears' vocals with that of Madonna's during her early days and Aguilera's with that of Cher's. Nathan Brackett of Rolling Stone commented that the release "improves upon American Life's standout single "Love Profusion", but the rest botches an opportunity to revive interest on its parent album". Fabian from Daily Breeze commented that Remixed & Revisited "is an amusing collection of novelties." Sarah Crompton from Boston Herald proclaimed the album to be "more fun than her full-length 2003 offering American Life."The Malay Mail said that the remixes from the album are for "true blue Madonna fans."
A writer for The Miami Herald was negative towards the release saying that "Madonna's latest misstep is this pointless Remixed & Revisited seven-track EP in which she tries to resell five songs from her recent American Life CD to an audience who deserve far better efforts from the queen, than this." Ricardo Baca from The Denver Post compared Madonna to actress Drew Barrymore on the cover of the EP, feeling that the singer looked foolish and that the tracks were weal attempts at "spicing up" the already non-commercial songs from American Life. Kevin C. Johnson from St. Louis Post-Dispatch said that with the remixes, Madonna "put some life" back into the songs of American Life, complementing "Your Honesty" and wondering why it was left from the Bedtime Stories sessions. Keith Caulfield of Billboard was impressed with "Your Honesty" and the remixes of "Love Profusion" and "Nobody Knows Me". He said, "Die-hard fans, even those unenamored of American Life will dig this EP." In his book The Essential Rock Discography, Martin Charles Strong called the release as "equally dispensable as its parent album".