Extraordinary Machine (Jon Brion version)

*Bootleg release

In late June 2004 the song "Extraordinary"—which had since been retitled as the title track—was leaked onto the internet. Soon after, a "rough mix" of "Better Version of Me" also leaked, with the following inscription listed as a comment in the properties of the MP3 file: "It has some good bits, but I still think we never have topped the second version. Ideally, we would combine some of this with that, but obviously we can't. Sigh. Ask the others what they think—I know she was partial to both of them, particularly the second". Josh Korr of the Tampa Bay Times wrote, "With a playfulness and penchant for odd sounds and instruments that channel the spirit of Brian Wilson's Smile, Apple's first songs since 1999 make Norah Jones, Joss Stone, Alicia Keys and other pretenders sound like American Idol rejects", while Entertainment Weekly called the songs "tantalizing, brazenly eccentric art pop … With Apple, the weirder, the better".

Fans in support of Fiona Apple demonstrating outside the headquarters of Sony BMG Music Entertainment in New York City on January 28, 2005.
After months of no official news, an article about Jon Brion appeared in an October 2004 issue of Entertainment Weekly. In it Brion is reported to have said that the album had been shelved since its completion in May 2003 due to the label not hearing any obvious singles. A representative for Epic Records stated that the album was to be released in February 2005, and that Apple had decided to re-record some of the songs. Brion later clarified the status of the album in an interview with MTV News in January 2005: he said that Epic had desired material in the vein of Apple's debut album Tidal (1996), but that when confronted by Machine, "it's just not the obvious easy sell to them". When USA Today asked Apple herself about when the album would be released, she replied: "You'll probably know before I do".

Shortly thereafter, Fiona Apple fans organized a week-long mail campaign to flood Sony with support for Apple and for the release of the album. In response to the campaign, Epic president Steve Barnett said: "It's our understanding that Fiona is still in the midst of recording her next album, and we at Epic Records join music lovers everywhere in eagerly anticipating her next release". On February 26, 2005 radio DJ Andrew Harms at 107.7 The End in Seattle began playing previously unheard tracks from a bootleg copy of the album, and before long, poor quality copies of "Not About Love", "Get Him Back" and "Used to Love Him" were circulating on the internet. Harms said of the situation: "this is pretty special … with an established like Fiona, to have that happen is pretty crazy, so to stumble upon a full-length copy of the record was incredible"; he also noted the positive response from listeners the songs had received.

By early March 2005 radio recordings of "Waltz", "Please, Please, Please", "Oh, Sailor" and "Window" had leaked online; those were followed by better quality album cuts of "Oh Well" and "Red, Red, Red". Soon after, CD-quality versions of all the tracks were released through the BitTorrent website TorrentBox. They received a positive review from the New York Times, who described the album as "an oddball gem", adding "Had it been released, Extraordinary Machine would have been a fine counterbalance to a pop moment full of monolithic, self-righteous sincerity." Ed Bumgardner concurred, saying the album was "certainly a work of daring and sophistication, as wildly imaginative as it is entertaining", while Will Dukes said "Extraordinary Machine flaunts a quirky, cold-world cohesiveness that's as inviting as it is alienating." According to the file-sharing tracking website BigChampagne in March, 46,759 people were sharing the leaked tracks on major P2P networks. The RIAA later contacted webmasters of sites hosting the files and asked them to be taken down, while the BitTorrent files subsequently vanished from the TorrentBox website.