Zkusil bych si na straně PHP změřit, kolik času zabere čekání na odpověď od externí služby.
Obávám se, že tahle hodnota bude rozhodující, protože naplnit dvacet řádků tabulky Ajaxem (i když nevím, kolik sloupců) by nemělo být vražedně pomalé.
Pak by byla každá rada drahá. Možná zvážit ukládání vyřízených výsledků (pokud se data nemění a nevadilo by to poskytovali SOAP). Záleží na konkrétní situaci.