Armazene-o como VARCHAR(36) se você deseja ter um ajuste exato, ou VARCHAR(255) que vai funcionar com o mesmo custo de armazenamento de qualquer maneira. Não há razão para se preocupar com bytes aqui.

Lembre-se de VARCHAR os campos têm comprimento variável , portanto, o custo de armazenamento é proporcional à quantidade de dados que realmente está neles, não à quantidade de dados que poderia estar neles.

Armazenando como BINARY é extremamente irritante, os valores não podem ser impressos e podem aparecer como lixo ao executar consultas. Raramente há uma razão para usar a representação binária literal. Valores legíveis por humanos podem ser copiados e colados e trabalhados facilmente.

Algumas outras plataformas, como o Postgres, têm uma coluna UUID adequada que a armazena internamente em um formato mais compacto, mas a exibe como legível para humanos, para que você obtenha o melhor de ambas as abordagens.