Ist das ein MySQL-Sortierfehler?

Scheint tatsächlich ein Bug in deiner Version zu sein.

Ich habe es mit MySQL 5.5.8 versucht und dort ist es richtig sortiert:

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.5.8 MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> select * from test order by title asc;
+----+----------------------------+
| id | title                      |
+----+----------------------------+
|  4 | ABCDEFGHIJKLMNOPQRSTUVWXYY |
|  3 | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
|  1 | record1                    |
|  2 | record2                    |
+----+----------------------------+
4 rows in set (0.00 sec)

mysql> select * from test order by title desc;
+----+----------------------------+
| id | title                      |
+----+----------------------------+
|  2 | record2                    |
|  1 | record1                    |
|  3 | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
|  4 | ABCDEFGHIJKLMNOPQRSTUVWXYY |
+----+----------------------------+
4 rows in set (0.00 sec)

mysql>