What you are asking is a little daunting. Here is why:
Would it be faster to store a hash of the value as well and instead index and search on that?
Creating a hash column and indexing sounds like a great idea. I have suggested that back on
March 03, 2013 : Possible INDEX on a VARCHAR field in MySql (See Suggestion #3)
Does that even make sense if the values are not guaranteed to be unique?
This would depend on the cardinality of that hash column. Since you said you will have millions of rows, let me express this in numerical terms:
SELECT COUNT(DISTINCT hashcolumn) ... against the table. For a one million row table, this count should be greater that 20. In other words, each distinct value should have no more that 50,000 rows (5% of the table rows). Any value that has more that 50,000 rows will cause the MySQL Query Optimizer to dismiss the index from being used and make a full table scan the preferred method for that hash value.
If hashing the values gives them a consistent length, would indexing that make queries faster?
I would say Yes and Perhaps at the same time. Why two answers? Indexing and using a hash column in place of a long column sounds brilliant against a MyISAM Table. You said you are using InnoDB.
When it comes to using Fixed vs Variable text, I would go with MyISAM over InnoDB
If the table is fairly-to-heavily used in Transactions, the table must stay InnoDB. You can take better advantage of your idea in MyISAM. You can go forward with the hash idea. Please make sure the PRIMARY KEY is single integer column (
BIGINT if you know you will exceed 2 billion rows. Otherwise, INT). I would do a major RAM upgrade and increase the InnoDB Buffer Pool size accordingly.