If you go into your User CP, there will be an option in there to store "sent" PMs. Make sure this is turned on. Otherwise, you will have no record of sending one, and maybe that is making you think they are not going through.
Scroll down to the bottom of the message and click on the little box that says "save a copy in my sent folder"... Simple as that.. Or you can go to the User CP and change the setting to always save a copy in your sent folder. This option is under "Settings & Options" and then under "Edit Options", it is listed in "Messaging & Notification". See how simple it is???