Je suggérerais d'utiliser un varchar(500). Même si varchar n'a pas une longueur fixe, la base de données doit réserver la bonne quantité d'espace. Vous ne devriez pas remarquer de différence de performances en utilisant varchar(500) sur 2xchar(255).
Vous allez probablement également entraîner une surcharge supplémentaire en joignant deux champs char.