Be very specific and short, and do not be generic. Do not copy-paste the same mail to everyone. You should make them understand that you have done a little bit of research on them. Try to go through some of their recent papers (very tedious and time consuming, but you have to do it), and talk about some specific aspect. You don't have to propose anything ground breaking in your e-mail, just try to show that you have done some research on them. Do not attach anything in the first mail, I have seen my professor getting very annoyed with all the attachments. Politely ask them in the last sentence "If you are interested, I can send you my detailed resume and unofficial transcripts". I had a very nice example specifically for computer science, from some professor's personal website. I will post it here if I can find it.
And yah, if someone specifically mentions not to contact them, do not do that. Also, in most of the cases they won't even reply ( I read somewhere that the e-mail to reply ratio is 30:1), but don't lose hope. If you can get one of them interested, you are all set for PhD.
Good luck!