Everyone used to have some moderating controls for Visitor Messages on his or her own profile and I'm pretty sure those are still there. Do your VMs have little white checkboxes at the top right, and is there a "Moderation" control at the bottom of the page?

Once the moderators approve a VM on your profile, everyone can see it. I'm not sure who can see it when only you've approved it.