Instead of XML, we could consider JSON (it's becoming more and more widespread). Otherwise a PHP implementation (multidimensional arrays?) seems ok.
Recently I've been working with AJAX plugins a LOT (custom implementation for a customer). I've already done some modification in the plug module to allow POST requests more easily.