MySQL Performance: MySQL => Need help for optimizing query

Hello!

I'm running a website where the members can manage their own music collection. The database is growing by each day and so the results of the queries too. Which makes some of them rather slow by this time. I need special help with one query, who reads all the cds, lps etc. of a members collection and sorts them in a user defined order (artist name first or cd title first etc.). Here are the main tables for this:

Table for artist information (excerpt):
---------------------------------------

CREATE TABLE `artist` (
  `aID` int(10) unsigned NOT NULL auto_increment,
  `aName` varchar(100) NOT NULL default '',
  `aFName` varchar(50) NOT NULL default '',
  `aLand` varchar(3) NOT NULL default 'XXX',
  `aBanned` tinyint(1) NOT NULL default '0',
  PRIMARY KEY  (`aID`),
  KEY `aName` (`aName`),
  KEY `aBanned` (`aBanned`),
) ENGINE=InnoDB;

Table for information about cds, lps etc. (excerpt):
----------------------------------------------------

CREATE TABLE `medium` (
  `mID` int(10) unsigned NOT NULL auto_increment,
  `uID` int(10) unsigned NOT NULL default '0',
  `lID` int(10) unsigned NOT NULL default '0',
  `mEAN` varchar(15) NOT NULL default '',
  `mName` varchar(150) NOT NULL default '',
  `mTypeName` varchar(30) NOT NULL default '',
  `mYear` smallint(4) NOT NULL default '0',
  `mYearOriginal` smallint(4) NOT NULL default '0',
  `mLand` varchar(3) NOT NULL default '',
  `mSampler` tinyint(1) NOT NULL default '0',
  `mBootleg` tinyint(1) NOT NULL default '0',
  `mBanned` tinyint(1) NOT NULL default '0',
  PRIMARY KEY  (`mID`),
  KEY `mYear` (`mYear`),
  KEY `uID` (`uID`),
  KEY `mSampler` (`mSampler`),
  KEY `mBootleg` (`mBootleg`),
  KEY `mEAN` (`mEAN`),
  KEY `mBanned` (`mBanned`)
) ENGINE=InnoDB;

Table which connects the artists with the media:
------------------------------------------------

CREATE TABLE `rel_am` (
  `relAMID` int(10) unsigned NOT NULL auto_increment,
  `aID` int(10) unsigned NOT NULL default '0',
  `mID` int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (`relAMID`),
  UNIQUE KEY `aID_2` (`aID`,`mID`),
  KEY `aID` (`aID`),
  KEY `mID` (`mID`)
) ENGINE=InnoDB;

Table which connects the users with the media:
----------------------------------------------

CREATE TABLE `rel_mc` (
  `relMCID` int(10) unsigned NOT NULL auto_increment,
  `mID` int(10) unsigned NOT NULL default '0',
  `uID` int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (`relMCID`),
  KEY `mID` (`mID`),
  KEY `uID` (`uID`)
) ENGINE=InnoDB;

Typical query for this:
-----------------------
(Sort all media in my collection by: sampler at the end, artist names first, year of release next and than the name of the record and it's type)

SELECT a.aID, a.aName, a.aFName, a.aLand, m.mID, m.mName, m.mTypeName, m.mYear, m.mYearOriginal, m.mLand, m.mSampler, m.mBootleg
FROM rel_mc AS mc 
LEFT JOIN (`medium` AS m, rel_am AS am, artist AS a) 
ON (m.mID = mc.mID AND am.mID = mc.mID AND a.aID = am.aID) 
WHERE mc.uID = 1
AND m.mBanned < 4
AND a.aBanned < 2
GROUP BY m.mID
ORDER BY m.mSampler ASC, a.aName ASC, a.aFName ASC, m.mYearOriginal ASC, m.mName ASC, m.mTypeName ASC 
LIMIT 0, 100;

A query of this type could take from one up to three or more seconds, depending on how big the collection of one user is.

The problem is: the ORDER BY can vary from member to member. So I can't put an index on the fields in the ORDER statement.

Any good hint how to optimize this is well appreciated.