I downloaded your sample exe and tested it on three different PCs (XP, Vista and 2000). I made sure that none had the Segoe font installed. When the pub runs, two font files are extracted to the Windows temp folder. One is Arial and the other is Segoe UI. Below is what the running pub looks like:
Embedding and temporarily installing fonts on the target PC is quite simple. All NeoBook does is extract the font file to the PC's temporary folder and tell Windows that the font exists (via AddFontResource). It's literally two lines of code. Now, there are a handful of fonts that, for some reason, simply won't work this way. It could be a bug in Windows or it could be a licensing/copy protection issue with the font. Segoe UI does not appear to be one of the fonts with problems, although I'm not sure what Microsoft's licensing terms are for this font.
One thing you might check is the following registry section to see if there are any substitutions that might affect Segoe:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\FontSubstitutes
Arial (C:\Program Files\Left 4 Dead\platform\vgui\fonts\arial.ttf)
Strange, he takes the arial from a game that is installed in my system... But the arial is not the problem.
Thanks to the game, that's where Windows is looking for the Arial font. Not a problem unless you decide to delete the game. Check the following registry section on your PC to see what other fonts might be messed up:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Fonts