On registration/login through Facebook, a user *must* accept your application and give permissions for 'basic' info like email address and birthday (if requested). However, the publish_stream permission comes up in a 2nd box that is completely optional. If the user clicks 'skip', they will not grant the permission to post to their wall but still be able to login.
We do ask for the publish_stream permission each time they'd log in (if they haven't already granted it), but if you're not posting on logins, even if they accept it later, the new user registration post won't be made.
Hope that helps explain. If some status posts are being made, but not all, that's almost certainly the cause. If none are being made, it may be something else.
Alex