Hrm, ignore my other thread post.    Anyway, the "to" vs "both" means nothing in terms of the transports.  Well, not in the way you are describing anyway.  msn.yourserver.org is the conduit through which all presence changes occur.  Direct-to-contacts presence notifications do not get through.  (for the most part, there's no reason to do this with the legacy contacts, they go entirely by a single setting, which is handled by msn.yourserver.org)  I am setting to "to" because it cuts down on needless traffic to the gateway (by a very very large degree).

Lets see...  MSN actually has a similar presence structure to XMPP in that there are "forward" and "reverse" lists that correspond to "to" and "from" in XMPP.  However MSN also has block and allow lists.  The person has to be authorized and placed on the "allow" list for the MSN contact to be able to see you online.  This step is performed when you add the contact back but now that I think about it, I don't believe that it's done on a simple authorization.  (in other words, you -have- to add them back for them to see you)  Does this sound like it might be what you are running into?