We've got about 3K Selenium tests, but we use Cucumber and its system of "feature" files. It works well for the quite complex cases where you could not record them (i.e. need to add database records, then check UI for the record). I suspect as your tests get more complex you will find cases where recording in the browser will not suffice.
Most Cucumber users (a.k.a. 'Cukers') use Ruby, but there is also
Cucumber-JVM (very active GitHub project) which is done in Java and Eclipse. That would probably be the best bet for GWT developers.
This might not be viable for your use case, but it might help other GWTers. :)
Sincerely,
Joseph