Axolotl has a well defined message structure using established crypto functions. All of them, for example, except Curve25519 are in Crypto++. You can probably fairly easily bake your own, albeit I'd use the olm from Matrix and just make theirs work well first.

Agreed that E2E is mandatory for privacy. The federated nature of Matrix doesn't make it any harder to implement though - after all, TextSecure/Signal has basic federation too. The one subtlety we have is that we want to give the users the option of selecting between PFS and replayable epochs of history on a per-room basis - the latter making it easier to sync history between devices; the former being for the privacy paranoid.

Now, a more interesting privacy concern is that Matrix doesn't and can't protect metadata currently - see https://matrix.org/~matthew/2015-06-26%20Matrix%20Jardin%20E... for details. So if you want both encrypted contents as well as obfuscated metadata, go check out Ricochet or Vuvuzela or Pond or something for now :)