Couple of thoughts to add, and votes for the above:
1) Get your bad self listed as one of those annoying ads that pop up in Morpheus. Since you're in some sense a competitor to Morpheus, that's probably a hard sell, but no doubt people who are into MP3s are using that program a LOT and the airtime of ads that it vomits is pretty high. Other efforts in similar directions like LimeWire or other file-sharers would probably pay big dividends.
2) Check out up and comers like mp3newswire.net. I go to places like this for info because theirs seems to be more up to date than the rest of the spooge out there.
3) The car-stereo-that-plays-MP3 business is seriously taking off. This is one of my primary motivations for ripping my CD collection and investing the time, $, and effort into MJ. This year's generation of products is probably, by sheer number of models that are coming, up about 300% from last year. Ford, I think, is even offering a factory model that plays MP3. These facts suggest a number of avenues to explore:
--See about bundling MJ with a car stereo.
--Put ads on car stereo sites like Kenwood and Pioneer, et al.
--Investigate partnering up with car stereo installers for some kind of a deal to bundle MJ or a discount for it with an installation or a purchase or something like that. Vague, I know, but that's the point of purchase for this kind of hardware and there's probably an inside track there to be found somewhere. Here in Portland there's a boatload of mom & pop car stereo shops that compete with the giants. The same is not true of other types of retail business. If more car manufacturers are going to offer factory models, maybe even DEALERSHIPS are legitimate targets for your efforts. Sounds silly on the face of it, but just thinking outside the box.
--The sites that review car stereos are also targets for ads. There's a site I go to called highwayMP3.com that's strictly amateur hour, but people who are looking for info about this kind of thing are there surfing it and reading their forums. I'm sure they'd fall all over themselves for an ad banner from you.
Doof is right about the retail thing. Retail is a dirty filthy awful nasty business, for sure, but the fact of having a physical presence there is huge for consumer perception. Physical ownership is hardwired into the human psyche. When a retail box is seen in a retail store, the perception is that you're solid enough to be able to accomplish that, and your product must similarly be solid by association. The collective consciousness hasn't shifted far enough yet so that the masses understand their product is equally good and possibly cheaper via download-only. Getting a retail presence might end up being a Pyrrhic victory for you, but may be worth at least examining.
Doof is, at the risk of being annihilated by loyalist fanatics, also right about the interface. I think Sonique demonstrates that it's possible to be simultaneously intuitive, highly functional, AND slicker than snot on a doorknob. Sonique is three years old and IMHO is still better looking and more innovative than just about anything else out there, for what specifically it does. I have faith that you guys can make it happen.
Along similar lines, the website and Interact also need to embody those same characteristics. The website ought to look slick like neoTropic's track info page does in the player. Graphically appealing like that.
And even further by extension, if you're going to start throwing ads around the Internet at some of these places, the ads should be just as slick. It occurs to me that a REALLY cool ad would be that if I clicked on it, I immediately started downloading MJ's trial version. Wouldn't THAT be a switch from having to wade through a bunch of garbage and filling stuff out like everybody else before the download starts. I should think you'd still be able to do this and get some useful information, yet provide that perception to the user. Like if you're hooked into .NET Passport and you're authenticated there, you go straight to the download as a user, yet you guys get the info if you want it.
No reason not to throw down the gauntlet with the ads, too. You're the Swiss Army Knife of this kind of software. More features than anybody else. Best of breed. Why not say so openly? The hell with those other weenies like MusicMatch. FIGHT! Dubious marketing practices, no. Just good old fashioned aggressive competition. All's fair in love and capitalism.
Getting bundled with a player or with a sound card would be great too. In my opinion you should just go to Creative Labs and say look, your included software BLOWS, why not fire your development team and outsource the job to us? Bundle our stuff instead! We'll make your name respectable again! And we'll have our guy Steve write your drivers so that it actually WORKS after consumers buy it!
--Severian