This is some strange problem that happens to me too but I'm guessing it's not Trillian's problem.
I have 3 Live (MSN) accounts set up. All of them are Gmail.
Say, before I start using Trillian, I have this very same problem just like you, on one account (Only one out of three) and it will randomly block newly added contacts (Especially when they add me, it gets auto-blocked but it seems like they can see me because they said 'hi' to me while blocked but then I had to unblock them manually.
It only happens on one account and when I moved to Trillian 2 days ago (Bought it when it was on sale and I love Trillian now!)
Let's say the problem still happens on Trillian, on the same account it used to have problem with old WLM 2010.
I don't know but I guess my problem originates from main WLM server and not Trillian's problem, at least this is very similar to your problem