I think you are using the same pump I used: the infamous "improved" one with the five-blade impeller.
I found that the slot in the shaft was sized for a no. 5 SAE key (1/8" thick), but a 3mm key was supplied. I got the right key, but then it didn't fit into the pulley well; I had to grind the edges of the key. I also found that the pump body interfered with the pulley and had to be ground down a little in a couple places. Finally, the nyloc nut and washer were not sized right; the nut would not thread onto the shaft enough to engage the locking part. All these problems can be fixed, as long as you know about them. But it's still annoying.
Yes, the pulley absolutely must fit tightly, with no wobble or slack.