Four videos were filmed for the album: "All Caps" (directed by James Reitano), "Rhinestone Cowboy" and "Accordion" (both directed by Andrew Gura), and "Shadows of Tomorrow" (directed by System D-128). "All Caps" and "Rhinestone Cowboy" appear on the DVDStones Throw 101 along with a hidden easter egg video for "Shadows Of Tomorrow" as a hidden feature. An impromptu video for "Accordion" was filmed in 2004 but not released until 2008's In Living the True Gods DVD.
At least two tracks on Madvillainy ("Rhinestone Cowboy", "Strange Ways") were produced using a portable turntable, a cassette deck and a Boss SP303 sampler by Madlib in Brazil. The first music to be publicly debuted from Madvillainy was the song "America's Most Blunted" which was played by Madlib at the Red Bull Music Academy in Brazil, November 2002.
An instrumental version of the album was released only in vinyl format and digitally through various online stores, with the tracks "The Illest Villains", "Bistro", "Sickfit", "Do Not Fire!", and "Supervillain Theme" being omitted. Two remix EPs of Madvillainy were released on Stones Throw. The remixes were done by Four Tet and Koushik.
In 2009, the album was selected in HipHopDX.com's Top 10 Albums of the '00s.Spin (p. 66) - Ranked number 17 in Spin's 40 Best Albums of the Year - "Madlib's production — thick, woozy slabs of beatnik bass — keeps things hotter than an underground volcano lair."
Rhapsody - Ranked number 13 on Rhapsody's 100 Best Albums of the Decade list and number 1 on the Hip-Hop's Best Albums of the Decade list. "The collaboration between underground hip-hop’s most adventurous producer (Madlib) and its most treasured lyricist (MF DOOM), Madvillainy is full of dark alleys and trapdoors. DOOM’s lines are extended vocabulary workouts and take repeated listens to fully unpack, yet there are times when the emcee peers through the Dada-ist carnival of words and speaks directly and honestly. Madlib’s production, meanwhile, is pure pastiche, a smorgasbord of world music, classic soul and outsider music. Snippets of childhood recordings rub against Sun Ra and Sonny Rollins. It’s a dark, funny and strange album."
Pitchfork ranked the album at number 13 in their list of the top 100 albums of 2000-04, commenting, "While Madlib's special power played tricks on your ears-- a sample you were sure was the sound of cars rolling by on the street might sound like the hiss of a record on a different day ("Rainbows")-- Doom unfurled his clever lyrics like a roll of sod on earth... and the album curved in on itself like a two-way mirror." Pitchfork more recently ranked it as the 25th best album of the 2000s.
In 2015, it ranked at number 2 on Fact's 100 Best Indie Hip-Hop Records of All Time.