I do not have any experience with MySQL, but in general there are a few more issues that can contribute to issues with queries, despite correct indexes. There is the issue with VARCHAR() type vs NVARCHAR() type. That is VARCHAR in a specific locale and vs NVARCHAR in unicode. Some databases create column types in VARCHAR() by default, but the java connector binds values as NVARCHAR(). This results in data-type promotion. This means that the values from the table/index are promoted from VARCHAR to NVARCHAR so this means that the index can not be used as an index, but has to be fully scanned. The same might be the case when performing join operations and there is a mismatch between PK and FK in respect to VARCHAR -> NVARCHAR.
Some databases store the collation of the data type with VARCHAR, so when you access the database with an other collation conversions might take place as well.
Performance issues are related to time and a process is spending time on the CPU or is waiting on something (IO, other process,...). So it would be nice if you can tell us what your system is doing when it is processing the long running query (CPU or IO). You can use task manager for this, but a much nicer tool is process explorer (procexp.exe) from
www.sysinternals.com (now days owened by Microsoft). These tools are a must for those windows users that have some technical courage
I suggest that you show us your table and index definitions and your queries, we might draw some conclusions from there.