wrote in his book, Madonna as Postmodern Myth, that "Beautiful Stranger" denoted one of the series of looks reinvented by Madonna around that time, and was a "radical" change from the geisha look of her previous video for "Nothing Really Matters", released the same year. Matthew Rettenmund wrote in his Encyclopedia Madonnica that "Madonna probably gave very little thought [behind the video]" but he felt that it was better than being a "couple of steps above a clips compilation". At the 1999 MTV Video Music Awards, the video was nominated in the categories of Best Female Video and Best Cinematography, and won for Best Video from a Film. It also received a nomination for Best Pop Clip of the Year at the 1999 Billboard Music Video Awards. The clip won Best Cinematography and Best Make-Up at the 2000 MVPA Awards; it was also nominated for Soundtrack Video of the Year. At the 1999 VH1 Fashion Awards, the video received a nomination in the category of Most Stylish Video. The video can be found on the Madonna compilations, The Video Collection 93:99 (1999) and Celebration: The Video Collection (2009). Live performances and covers Madonna performed "Beautiful Stranger" on her 2001 Drowned World Tour, where it was the fourth song on the setlist. It began with an introduction by Myers as Austin Powers on the video screens, the singer then asked the crowd "Do I make you horny?" (one of Powers' catchphrases) before performing the song. She was joined by backup singers Niki Haris and Donna DeLory, who also contributed with background vocals on the track. Costumes for the performance included spiked dog collars, Swarovski crystal-encrusted bracelets and tattered tops; Madonna herself wore a sleeveless black top, crossover top with one net sleeve, jeans with zips and bondage straps and a tartan kilt. The backdrop during the performance displayed scenes from the movie and psychedelic fluorescent whirls. It also featured a lost technician at the end and elements of "Soul Bossa Nova (Dim's Space-A-Nova)", another song from the film's soundtrack. On September 15, 2001, the tour's final date, Madonna's then husband Guy Ritchie joined her onstage as the lost technician. Michael Hubbard from MusicOMH noted that "things quickly hotted up with [...] 'Beautiful Stranger'". The performance on August 26, 2001, at The Palace of Auburn Hills, outside of Madonna's hometown of Detroit was recorded and released in the live video album, Drowned