Does the 3CX Activity Log show that the calls do not match an outbound rule? (May have to set logging levels to Verbose.)
Does the rule you created, have + as the first character, or is it simply 12 digits?
Have you tried enabling/setting up E164, on 3CX, to deal with converting the + to the correct prefix, depending on the type of call?