Since there are so many fields with data from multiple sources, we have queries running searching on individual fields. Due to this we need to have many indexes. 4GB of the 8GB is the size of the index itself.
Are you sure you've read up on your C. J. Date? I've had that once before: someone complaining that "queries take too much time" with a paltry single-digit-GB database. When I asked about the specifics, the only repeating reply was "we can't tell you". You don't mention anything of value, but querying a few million records can't possibly take a few minutes on the aging desktop computer I've bought seven years ago, much less on a modern server.
Selects per hour: 37K Updates per hour: 170K
While the speed of selects or updates by the background crons was and is not important, the speed of selects run by the users on the same table was important. The easy solution was to cache the data so that the users could search domains at a good speed. The memory table just worked brilliantly as a cache.
(I'm no mysql guru and its my first project where MyIsam did not work for me, so I know I definitely could do a better job of optimizing the Innodb table and Innodb settings in my.cnf)
How's the disk io on that linode VPS?
If it were me, I'd split that one giant table into a "main" table with some basic information and foreign keys pointing to other tables with the more detailed information from the other sources.
In our case, joining 6 tables with 14 fields each is going to be much slower than running the query of just the table.
This is a great problem that would be fun to work on. Except that I guess you already found a satisfactory solution.