... for a page which is heavily ajax-based.
Eu mesmo tive esse problema. Ferramentas baseadas em HTML, como iMacros ou Selenium IDE não funcionará de forma confiável com páginas da web complexas porque elas precisam de uma página estável para encontrar seus elementos, não aparecendo e desaparecendo código javascript (como você disse).
Mas tive bons resultados com Sikuli e Kantu Visual Browser Automation , que é como o Sikuli, mas dentro de um navegador da web Chromium. Ambas as ferramentas usam o reconhecimento de imagem e simulam cliques reais do mouse , para que funcionem bem com aplicativos da web pesados de ajax!
A diferença é que o Sikuli é executado na área de trabalho, mas o Kantu é executado dentro do próprio navegador, portanto, ele não ocupa a área de trabalho e você pode continuar fazendo outras coisas enquanto está em execução.