Lo tengo!!!
He encontrado una solución bastante buena aquí: http://stackoverflow.com/questions/6130237/javascript-function-to-parse-html-string-into-dom
La segunda respuesta, escrita por Brad Christie.
Básicamente los pasos son los siguientes:
1. Crear un <div> oculto.
2. Enviar desde el servidor los datos de las nuevas filas con formato de tabla (incluir el <table).
3. Colocar la respuesta AJAX dentro del <div> oculto.
4. Referenciar, a partir del <div>, al <tbody> interno (.firstChild.firstChild).
5. Mover con appendChild el <tbody> a la tabla visible.
Lo he probado y va más rápido de lo que parece a priori!
Muchas gracias a todos los que le habéis dedicado tiempo :)