I know Jens have a lot of experience in this however I think you can get this working.
I have the following rules in a production system:
^00(\d{5})$
00$1
Then I also have a routing:
^00(\d{5})$
This let my users call the same way as they did before and I also have normalization rules for E.164.
What if you change the rule to:
^2(\d{8})$
Translation pattern:
02$1
And then add a route for that, could you test it?
Might be specific to what gateway you are using but for my setup it workes to send both "normal" numbers and E.164.