Locke's speed might make him good as the ultimate killing machine, but that type of uber character isn't necessary for anyone to beat this game. If you like seeing how much damage one guy can do, that's one thing, but for all practical purposes there's not much reason for it.

Anyway, Gem Box + Ultima + Ultima = most powerful strategy for the most-difficult battles. Maybe throw a Quick in there for extra Ultimas. A character with high MP (or Terra in Esper Form) will cause max-damage to every enemy on the screen uniformly. So for a single enemy the Locke strategy might get you more damage, against several enemies, the total amount of damage caused by chained Ultimas will far exceed what Locke can accomplish.