A database is definitely sounding like the appropriate way to go. However, you cannot just shove data into it and expect it to magically go 10x faster. I know you know this, but data stored in a relational form often requires a complete rethinking of the code that uses it. I ran into this recently, so I thought it might be useful for you to be reminded of that. An RDBMS is not a drop-in replacement for anything other than another RDBMS.

Basically, if you need a 10x speedup, you need to approach the problem from scratch, looking at first principles. It sounds like you need to rethink how you organize your data so that it is more efficient for your normal lookups. This means you need to evaluate what kind of questions you're asking. Often, we think we know the kinds of questions we're asking because it's been working for years, but we're really asking the questions in a slightly different way, which can mean all the difference in the world. This may mean rewriting the code asking the questions, and possibly even how you gather the questions to ask from the user. (Maybe a "holdings file" isn't the appropriate way to handle things ...)

Basically, the only items you should be keeping when doing this effort are

1. The raw data
2. The finished product

Very often, I find one needs to completely transform the raw data into something else in order to facilitate lookups. Once, I needed to perform three transformations in order to get speed where it needed to be.

Something else to keep in mind - that 10-15min isn't for one query - it's for N queries. That translates into M queries/second where you're currently at K queries/second. I'd focus on getting K to M, instead of the whole thing at once. Trying to deal with thousands of concurrent items is ... well ... daunting.

As for MySQL-isms, have you considered turning the query_cache on?