I did phone them. I got a very non-interested person on the other side of the line who just told me bluntly that I had to pay, nothing to do about it.
He was so uninterested that I could actually hear him think : "oh god no, not another one of those freeloading bastards who wants to get away with not paying"
When I told him I had paid and signed for receiving the package and that surely they must be able to find a trace of that in their archives, he just told me that wasn't possible and that I just had to pay. He then just hung up.

I was practically fuming when that phonecall ended.

So I made a call the the juridical department of a consumer magazine (on which I'm subscribed), and they told me to just write them a letter in which I state that I don't agree with what they're saying and that I don't intend to pay twice for the same "service".

I've just written the letter. Am going to the post office now to send it by registered mail.

I've decided that there's no way that I'm going to pay that amount just because they either have a thieving staff or a lousy accountancy section. I will take this to court if I have to, if only because it's a matter of principle.