You don't have to encrypt the entire body of a message with WSE.  You can encrypt just certain pieces.  Or you can encrypt some pieces with one key and other pieces with another key.  You can find code that shows you how to encrypt part of a message here.

For those of you following my blog directly, this second post is because the first one messed up the formatting on the MSDN Web Services Developer Center.

   -Matt