Binary protocols can be extensible! There is one particular protocol I want to cite, but the application which it powered has been dead for years, and I can no longer find the protocol doc. The application was called HotLine, and it used an extensible binary protocol; it used application-level packets, and inside of the packets there could be any number of fields which were given type by an INT_16 (types could be "username," "flags," etc). Towards the end of its life (in the last revision of the protocol), they added a packet that allowed an administrator to view and edit *all* of the user accounts that the server maintained - to do this, they took the "read/write a single user" packet, and placed the entire packet's payload inside of a field, enumerated that over every user, and sent it as one huge packet.
The original argument against XML (made by MF) was that it generates a lot of pointless overhead - in addition to that, it takes longer to parse that overhead because it is a variable length string. I'm with you in your argument that an extensible protocol is favorable, but XML would not be my recommendation - the BNCS servers do need to take efficiency wherever they can get it.