Consulta lenta en mysql

Tengo un problema a raíz de un incremento del 500% del número de mis anuncios... De repente las consultas van muy lentas. He estado intentando optimizar dichas consultas, pero he detectado que el order de la SQL hace que pase de décimas de segundo a 8, 9 o llegar incluso a los 19 segundos.
Te estaría eternamente agradecido si me pudieses echar un cable.
La tabla en cuestión es:
CREATE TABLE `cars` (
`id` int(11) NOT NULL auto_increment,
`makeId` int(11) NOT NULL default '0',
`modelocationId` int(11) NOT NULL default '0',
`version` varchar(255) default NULL,
`provinceId` int(11) NOT NULL default '0',
`locationId` int(11) default NULL,
`price` int(11) NOT NULL default '0',
`content` text,
`email` varchar(255) default NULL,
`showEmail` tinyint(1) NOT NULL default '1',
`applyUrl` text,
`creationTime` int(14) default NULL,
`activationTime` int(14) default NULL,
`expirationTime` int(14) default NULL,
`image` text,
`difusion` tinyint(1) NOT NULL default '0',
`template` tinyint(1) NOT NULL,
`languageId` char(2) NOT NULL default '',
`visitas` int(11) default '0',
`status` tinyint(1) default '0',
`site_origin` int(11) NOT NULL,
`ipAddress` varchar(50) NOT NULL default '',
PRIMARY KEY (`id`),
KEY `locationId` (`locationId`),
KEY `makeId` (`maked`),
KEY `modelocationId` (`modelocationId`),
KEY `provinceId` (`provinceId`),
KEY `language` (`languageId`),
KEY `image` (`image`(300)),
KEY `status` (`status`),
KEY `activationTime` (`activationTime`),
KEY `image-status` (`image`(300),`status`),
KEY `email-status` (`email`,`status`)
) ENGINE=InnoDB;
ALTER TABLE `cars`
ADD CONSTRAINT `FK_cars` FOREIGN KEY (`languageId`) REFERENCES `languages` (`languageId`);
y la consulta que da problemas:
SELECT c.id,c.content,c.price,c.image,m.make,mo.model,c.version,p.province
FROM cars AS c
INNER JOIN publication AS pub ON c.id = pub.carId
INNER JOIN makes AS m ON c.makeId = m.makeId
INNER JOIN models AS mo ON c.modelId = mo.modelId
INNER JOIN provinces AS p ON c.provinceId = p.provinceId
WHERE pub.pubstatusId = '3' AND pub.siteId = '1'
ORDER BY activationTime DESC
LIMIT 0,15;
Las tablas relacionadas tienen indices en los campos mediante los cuales hago las uniones (por ejemplo, indice en makes.makeId ...)
Actualmente estoy barajando del orden de 50000 anuncios activos.