Never, Ever, use Xpath Selectors
Never, Ever, have a Test Suite Larger than 20 tests
The other big speed up that we achieved at CustomInk was to take one huge Test Suite and break it up into many small Test Suites. This change helped across all browsers. Chunking up the tests and resetting the browser before starting on the next suite allows all of the memory that was being used/leaked to be cleared out. At CustomInk we fooled around with a lot of different suite sizes and found that 20 was about the right size.
With these two simple rules CustomInk was able to get a 15x increase in performance. Even with these changes our IE6 tests still take 5x as long as our Firefox tests. If anyone has any other performance tips/tricks please post them and share with everyone.