Как правильно спроектировать протокол обмена данными между клиентом и веб-сервисом?
Во-первых, забудьте про XML, его придумали бюрократы. Вот пусть они его и используют в своих банках и налоговых. Для парсинга и кодирования JSON достаточно пары функций по 10 строк каждая. Для парсинга XML, даже если в нем пару значений, нужно подгружать монструозные библиотеки.

Во-вторых, раз уж вы делаете веб-приложение, используйте возможности протокола HTTP. Это значит идеология REST, а не RPC. То есть вместо каких-то там «процедур» или «функций», вы пляшете от объектов и стандартных действий. 
Например, у вас есть объект с идентификатором obj_id. Для любого доступа к нему используется URL вида

example.com/path/to/obj_id

Далее по этому URL-у возможны 4 действия (http verb):
GET example.com/path/to/obj_id — получить данные объекта
PUT example.com/path/to/obj_id — изменить объект
DELETE example.com/path/to/obj_id — удалить объект
POST example.com/path/to/ — создать новый объект в папке /path/to
GET example.com/path/to/ — получить все объекты в папке /path/to

В зависимости от результата операции, вы должны возвращать правильные коды ошибок (200 OK, 404 Not Found, 403 Forbidden и т.п.).

Параметры более сложных запросов идут как get-параметры, ну например
GET example.com/path/to/?search=blabla
 — искать объекты
Или можно часть параметров перенести в урл:
GET example.com/my/report/01.01.2011-31.12.2011/
Я подумал было, что имеет смысл использовать для этого XML, ибо сейчас все так делают — наверно неспроста. Но, поизучав эту тему, понял, что при таком подходе принято и параметры запроса на сервер передавать в виде XML.

Не совсем понял как Вы себе представляете GET запрос на сервер с XML данными.
Ответ от сервера в виде XML — общепринятая практика. Используется в платежных системах повсеместно.