i seem to remember reading an interview (with keith mcmillan?) about his "kbow" / max/msp project. they discovered that you have to build custom bluetooth stuff because the bluetooth shipping with laptops / desktops is no good, as you say, variable blah blah. might be worth searching for that interview (i think it was on THIS site) or browsing his website: http://www.keithmcmillen.com/
Make sure it as new as possible - v2.1 EDR. Not sure if newer stuff is out. Some have better antennae then others, and make sure there are no major blocks between send/rcv. Experiment with orientations as well. And make sure theres not too much other 2-4 gHz stuff around.
Never used it with Max (control with WiFi, USB, MIDI here), but I'd look into the D-Link Bluetooth adapter. I got one for an old iBook that needed bluetooth after I got a Belkin adapter that didn't work well--no problem with with the D-Link.