Hey,
I just wanted to report that I am having the same problem. First I figured out that it's because of old version but recently having tried with both updated warband and latest ver of NW I'm still having the problem. Seems almost as it is random since I've had this problem few times before and then had a good streak without any problems. Usually I can be on the server for from 10 seconds up till 5 minutes after I get kicked. None else seems to have the same problem because filled up server has 199 slots left after I've been kicked.
I'm using the non-steam version.
edit: oh yeah and checked the registry for the correct cd-key. Could there be a description of kicking if it's related to cd key? Would help a lot narrowing it down.