Sua ideia de fazer hash de strings longas para criar um token para pesquisar em uma loja (cache ou banco de dados) é boa. Eu vi isso feito para cordas extremamente grandes e em ambientes de alto volume, e funciona muito bem.

"Qual hash você usaria para esta aplicação?"

• Não acho que o algoritmo de criptografia (hashing) realmente importe, pois você não está usando hash para criptografar dados, está usando hash para criar um token para usar como chave para procurar valores mais longos. Portanto, a escolha do algoritmo de hash deve ser baseada na velocidade.

"Você calcularia o hash no código ou deixaria o banco de dados lidar com isso?"

• Se fosse meu projeto, eu faria o hashing na camada do aplicativo e depois passaria para pesquisar dentro da loja (cache, depois banco de dados).

"Existe uma abordagem radicalmente diferente para armazenar/pesquisar strings longas em um banco de dados?"

• Como mencionei, acho que, para sua finalidade específica, sua solução proposta é boa.

Recomendações de tabela (somente demonstrativo):

user

• id int(11) unsigned not null
• name_first varchar(100) não nulo

user_agent_history

• user_id int(11) não assinado não nulo
• agent_hash varchar(255) não nulo

agent

• agent_hash varchar(255) não nulo
• browser varchar(100) não nulo
• agent texto não nulo

Algumas notas sobre o esquema:

• 
  Do seu OP, parece que você precisa de um relacionamento M:M entre usuário e agente, devido ao fato de que um usuário pode estar usando o Firefox no trabalho, mas pode mudar para o IE9 em casa. Daí a necessidade da tabela dinâmica.
  
• 
  O varchar(255) usado para agent_hash está em debate. MySQL sugestões usando um tipo de coluna varbinary para armazenar hashes, dos quais existem vários tipos.
  
• 
  Eu também sugeriria fazer agent_hash uma chave primária ou, no mínimo, adicionar uma restrição UNIQUE à coluna.