try a shop vacuum
Try colonoscopy tool. Flexible snake with lighted camera and a tool for removing obstructions. Like plumbers use to scope out drains
I love the idea of the plumber type tool! However, I dont really have one around myself. This may sound silly n simple…You’ve tried a coat hanger, but how about some bubble gum on the end? chew the crap out of it really quick so it gets solid, but not too long to get the sweet-sticky out of it. It needs to be sticky enough, as well as solid enough to hold its form so its not stringy. I hope that would help without having to take the seat out and pay outrageous labor costs. Oh, and when the gum gets stuck to the carpet (which im guessing it will) baby oil or olive oil is a less stinky solution than peanut butter. Good Luck! 
Try a good magnet. The phone might have enough metal in it to catch on to it.
The E36 seat is very easily removed. You need a metric socket set and about 30 minutes. Disconnect the car’s battery first (in the trunk), to avoid airbag lights. Loosen the 4 large bolts at the base of the passenger seat and remove it from the car. Then you’ll have full access to the air duct and the surrounding carpet. I’ve gotten quarters out of mine, so I’m pretty sure your cell phone will make its way back out.
Make sure you tighten those bolts when you put the seat back in place.
If you think you might do more work on your M3, I highly recommend the Bentley repair manual.
Several tool makers (DeWalt, Milwaukee, General) make scopes with a 4’ reach for under $200 new. It’s a handy tool to have anyway. A actual plumbers scope is a bit overboard, and would be pricey to hire the plumber or rent one. He might be able to rent one of the 4" units, or post on a site like CL to rent one or pay someone that has one $20 to give it a shot at retrieving it. Use it in conjunction with a part grabber or coat hanger with some stickum on it. If the phone’s moved more than 4 feet it’s going to need more than a grabber or coat hanger and the seat, et al are going to have to come out to fetch it.
I also had the idea of the inspection camera after having seen one in use recently by my plumber. You can find an inexpensive setup via USB connection to a Notebook PC for about $70 on “amizone”.
A second idea similar to the bubblegum on a stick is to but a Velcro tape setup that has both side in tape form. Peel the backing off to expose the sticky side and get it to stick to the phone…then wiggle the phone out. Of course looking at the replacement duct would be most helpful.
mrbeel beat me to the punch but a powerful shopvac with a narrow nozzle on the end. Do Not go to a commercial car wash if you want your phone back.
Try the vacuum method and get some vinyl tube from Home Depot or Lowes and duct tape them together to reduce the hose diameter. Stuff some rags to close the other vents on the duct to obtain more suction.
Another option is to secure double sided tape to your flexible “claw” and carefully guide it to your phone and pull it out. The only problem to this is that it has to be really secure otherwise you might loose the double sided tape in the duct. A diagram for a 1995 325i air duct is available here:
http://www.realoem.com/bmw/showparts.do?model=CB43&mospid=47498&btnr=64_0192&hg=64&fg=05
If it is not the right model of your car, you can obtain the correct one at http://www.realoem.com
Don’t tear up your car. Get a new cell phone. Your company plan may even give you one. And don’t worry about unnecessary phone rings. How long will that battery last?
You simply take the seat out to get to it. Four bolts and a couple connectors for heaven’s sake. The guy is an engineer. Righty tighty, lefty loosey. I guess first I’d try a piece of Romex that would be a little thicker than a coat hanger to nudge it out, but really, I used to pull seats out just to shampoo the carpet. No big deal as long as the air bag doesn’t go off.
I like the vacume idea. I have also had pretty fair results in similar situations using something very sticky on the end of a flexible extension. Gorilla Tape often works for me. Perhaps vacume first to get most of the dusty stuff out…The vacume with a sealed connection at the vent opening (duct tape)along with the blower and all the other vents blocked has real possibilities.
The shop-vac is the right approach. You will need on of those long plastic funnels (for transmission fluid) to step the size down small enough to fit in the vent and consequently increase the amount of suction. If you hear the shop-vac struggling, you may need to add some small holes to keep from burning the shop-vac motor up.
The solution is simple. A sticky mouse trap and a paint stir stick. Remove the unsticky sides of the sticky mouse trap. Lay a bout 2" of a paint stir stick in the sticky portion so it resembles a hand fan. Slide the stick trap into the duct and it will grab the phone. Don’t use the phone right away as you will need to clean the stick stuff off.
being an engineer, and not wanting to hack it do it the right way, even if it takes you a while having no passenger seat won’t prevent you from driving.
Download this Bentley .pdf Basically a factory manual for your car, in theory you could take your car apart to the last bolt with this.
You could try covering/plugging all the vents for the heater (dashhboard, under the other seat, etc)
and then turning the blower on full. Might not work, but you don’t have to tear up anything. DR
This is a fairly common problem in the medical field, basically a ______ is stuck in my _______. There are a couple of ways to solve this problem.
It sounded to me from the show like you had already tried directly visualizing and trying to get it out with a grabber, This is the most effecient way, but would likely be difficult since you won’t be able visualize.
The coat hanger with bubble gum idea is interesting, but I would suggest a slight variation on it, get a thin wooden stick, and apply a generous bead of quick drying superglue to the end of it. If you can visualize the close end of the phone, put the glue and the wood on the phone, wait for it to dry, and pull everything out. I suspect that this won’t work however.
What I would try is: go to your local medical supply store and buy 2 urinary catheters. These are basically flexible tubes with balloons on the end. Advance the tubes past the cell phone on either side, blow up the balloons, and pull back. This should bring out your obstruction with no problems. If you’re having trouble getting the catheters around the phone, you could try one with a coudet tip, which basically is a little stiffer and an upturned end, which allows you to navigate a little better.
Hope this helps.
Though the creative means to remove may be more fun, go with seat removal. It will give you full access to the area and not require luck! Or damage to the car. Folks, though an engineer, not all are mechanical engineers! My son is a computer engineer and can barely identify a screwdriver. DO THIS: Find your local BMWCCA (BMW Car Club of America) contact. Buy the Bentley book. You can get TONS of expertise for free, have someone watch over your shoulder, borrow tools or a garage, and make new car enthusiast friends in the process. They would love to help you.
Take the car to any parking garage in NY city. The phone will be embedded in either the rear seat or firewall when you get it back.
Without knowing much about the car or how tight the space is, I have a thought…
Every now and then I’ll lose some cables, little tools, USB keys etc… from around the house never to be found. I have a 3 year old son, and suspected that he threw them in the trash. But, later one day my cell phone goes missing… I call the phone and I hear it vibrating in the family room, near the entertainment center. On further investigation, I realized that the cell phone is in my subwoofer at the bottom of the bass port. I realize that my son put it there, but I couldn’t take it out because my hand wouldn’t go in far enough. Ended up having to wait for my son to come back from pre-school, and to coax him into getting the phone out for daddy. Voila… there comes the phone, the cables, USB keys, coins, rubber bands, a compass, some of my wrench sockets.
Well, my suggestion is to find a little kid and dangle an ice cream in front of him and convince him to help you get it out