Toda mi investigación finalmente culminó en la conclusión de que, si bien EF en general es malo para el rendimiento, MySql+EF es francamente de mala calidad. La elección de SO de L2S sobre EF es un buen movimiento y si tuviera acceso a una base de datos MS Sql en lugar de MySQL, también me habría movido en esa dirección.
Desafortunadamente, estoy atascado con MySql porque es gratis y eso me ha obligado a renunciar a EF. Ahora he vuelto a codificar mis consultas SQL de la manera antigua, probada y eficiente, y los resultados son buenos.
Aprobé MYSql + EF, pero me encantaría saber de personas que lo hayan usado con éxito en un proyecto no trivial.