What printer are you printing to? Type, model and firmware are helpful, as well as driver revision...
Why do you add font's through policy? and why not have the policy modified to not replace those fonts if they are missing.
Check these keys to see if something might give you an idea...
HKLM/software/Microsoft/WindowsNT/CurrentVersion/FontSubstitutes/MS Shell Dlg
HKLM/software/Microsoft/WindowsNT/CurrentVersion/FontSubstitutes/MS Shell Dlg 2
Good Luck