Совместил вместа архивы старых и новых мессаг (получилось более 67 тысяч сообщений) и прогнал новый возможный алгоритм хеширования с отбрасыванием 2 нецифробуквенных символов вместо замены (и с добиванием хвоста нулями, если вдруг надо будет):

base64.urlsafe_b64encode(hashlib.sha256(msg).digest()).decode("utf-8").replace('-', '').replace('_', '')[:20].ljust(20,'0')

В итоге распределение букв в сформированном таким образом msgid стало плюс-минус равномерным:

0 1072
1 1110
2 1064
3 1026
4 1117
5 1139
6 1049
7 1084
8 1055
9 1075
a 1108
b 1081
c 1093
d 1108
e 1089
f 1052
g 1104
h 1111
i 1076
j 1124
k 1094
l 1090
m 1151
n 1083
o 1047
p 1116
q 1132
r 1029
s 1117
t 1090
u 1073
v 1061
w 1061
x 1129
y 1096
z 1103
A 1002
B 1024
C 1016
D 1089
E 1144
F 1061
G 1045
H 1081
I 1090
J 1107
K 1113
L 1065
M 1122
N 1141
O 1050
P 1019
Q 1125
R 1063
S 1031
T 1115
U 1122
V 1076
W 1121
X 1020
Y 1113
Z 1077

Коллизий не обнаружилось (зато нашлись несколько одинаковых сообщений у которых были разные msgid) и по итогу около трети сообщений сохранили свой старый msgid (т.е. там небыло этих двух символов на замену, которые в этом алгоритме просто отбрасываются)

Это я думаю а не поменять ли алгоритм хеширования на своей ноде, раз уж и так кто как делает...