This is a nice benchmark that has been broken down by scaling (albeit being an older article): http://www.mysqlperformanceblog.com/...hmarks-part-1/
It should help you choose which type to use. INNODB wins overall here with very few drops in the scaling below the myisam. If you were to increase it and follow this existing data graph, it would likely show an improvement of myisam for large recordset's with fulltext searches over the innodb. But otherwise, it would indicate that innodb will scale better.
If your keys are correct, make sure you check your datatypes. If a query doesn't match the datatype and the mysql isn't set on strict datatype mode, then it needs to cast the datatype each time its used. If it expects a number and you give it a string, it will cast each field into a string to compare it to your string. Doing this becomes noticeably slower as the recordsets increase in size.