Во втором примере URL не относится к конкретному ресурсу, поэтому ИМХО это не RESTful.
Если вы исправите это, выбор сводится к форме и кодированию XML.
Если вам нужны структурированные и расширяемые данные, тогда может пригодиться XML:
<phone type="work, mobile"><num>555-555</num><ext>123</ext></phone>
но не обязательно:
phone=555-555&phone-ext=123&phone-type=work&phone-type=mobile
Многие пользователи API могут неправильно понимать кодировку XML, им трудно понять, что такое косвенное обращение к пространству имен, поэтому кодирование форм может быть лучше для широкой аудитории.