Ok, I tried it and got what you were talking about. It's just bad technique! If I try at a fast speed with good form, I get the dialogue. If I try to go so fast that it's just a big key mash then it doesn't go through. I have to do it so fast it's almost a spaz movement and I'm certain I'm just hitting the keys wrong.

How about just teaching them to remap their shortcut? Bring up options, Customize Ribbon, Keyboard Shortcuts, All Commands on the left, Paste* commands on the right.