Мне интересно ваше требование "клиенты с брандмауэрами". Сокеты с двоичными данными или XML через HTTP могут использовать любой порт (не только порт 80), и мне интересно, будет ли ваше устройство «прослушивать» сеть или просто устанавливать исходящее соединение. Если ваше устройство прослушивает, вам нужно открыть порт на брандмауэре. Установление исходящего соединения («звонить домой») намного проще на брандмауэре.
Так что я думаю, что вы могли бы использовать сокеты и двоичные данные. Тем не менее, я столкнулся с похожими проблемами в последних двух проектах, и я действительно хотел реализовать WCF с использованием REST на встроенном устройстве, но никто больше не хотел это делать - я надеюсь, что кто-то еще будет первым, и опубликует некоторые результаты !
Удачи! (и опубликуйте свои результаты!)