I found the solution. It seems that using AddUniqueDynamic instead of AddDynamic made it work.
I made sure I was only binding the delegate once, so not sure if the engine did something underneath. Anyway here is the code that works just in case someone encounters this issue:
AnimInstance->OnPlayMontageNotifyBegin.AddUniqueDynamic(this, &ABaseCharacter::OnAnimNotifyBegin);