Сегодня наткнулся на интересную мысль по этому поводу, которая заключалась в следующем:
1. Для максимального быстродействия база должна храниться в ОЗУ.
2. Если база большая, то есть вероятность, что записей с VARCHAR (255) в ОЗУ поместится больше, чем c CHAR(255).
3. Если база маленькая, то только CHAR.
4. Кстати MySQL все (длинные) CHAR будет хранить как VARCHAR, если в табличке есть хоть одно переменное поле (BLOB, VARCHAR, TEXT)

С уважением,
Илья Винокуров.