Ramtin,
assuming you want to really do this job, give a look at this: Remixing and Remastering with R-MIX SONAR – A Case Study by Noel Borthwick: http://blog.cakewalk.com/remixing-and-remastering-with-r-mix-sonar-a-case-study-by-noel-borthwick/
Hope it gives you some ideas...

Let's say you could filter every instrument out perfectly to the point where melodyne could make q decent midi out of it.  It would still be far more work than actually sequencing it.  Even the best forensic audio engineers in the world would be hard pressed to isolate every sound in a typical song cleanly enough to get midi track equal to even an amateur attempt to transcribe . I do like a challenge though, so here is what i propose.  A task like this is beyond arduous, but split up could end up being only a slight waste of time .  Post the song you want to attempt this wit hand then have one person attempt to isolate each instrument as best as possible. Some instruments will be possible and may yield good results.

Exact MIDI copy of anything you want. $300.  

I would like an exact midi copy of 4'33"

If it's possible (which I doubt), it would be better to start with something higher-quality than an MP3 file, e.g. a WAV.
 

^ true.  I think best case scenario is that one is able to extract some instruments and use the midi data from those files to build midi files for the other instruments.  Getting one clean instrument may give you enough info on key and chord progression to help fill in blanks.

Clint Swank
Exact MIDI copy of anything you want. $300.  

Allan Holdsworth - Mac Man
Bill Bruford - Fainting in Coils
 
Give those a listen and let me know about transcribing to midi, including guitar solos and all other instruments.
 
I'd even give you a head start - I have recreated all instruments other than guitar in midi for the Fainting in Coils tune, in particular the lead lines Holdsworth plays.
 
I'd love to see it, but don't think that's likely to be doable.
 
Bob Bone
 

Although I've actually done stuff like this in the past (for money! as well as my own edification), I was mostly kidding.  Aside from actually playing the Holdsworth stuff, which I can't quite do, getting the pitchbends accurate in midi would be a huge chore.   That said, I think one of those tunes would be more like a grand.

I know - I picked out a couple of pretty extremely challenging tunes.
 
As I said, for that Fainting in Coils tune, all the rest of the instruments are already recreated with midi tracks - it's just the guitar lead parts for that tune - crazy playing on that one.
 
But yeah, for the Mustang Sally kind of stuff, no sweat.  I would sequence that kind of stuff up all day for $300 a tune.
 
In the meantime, I guess I'll continue to do as I have done, painfully sequencing up what I can.
 
Bob Bone
 

Mustang Sally, well, hardly.  I once did Green Earrings on an Alesis MMT-8.