I installed FCR and picked the hardest difficulty.

The small assassin enemies during the prologue parry every single attack.

I can kill the big guys with the strong combat style but the small enemies parry every attack even though I use the fast style.

I tried side stepping and jumping over them, moving a bit or waiting for them to start their animation but nothing helps.

Is this a bug?

Sounds like a feature of FCR (I haven't tried it). Have you read the full instructions?