Ok, upon reading some other messages, it does appear that Safari isn't reading the entire font list. You can, however, fix it by modifying the Fonts.plist file, which is located in this folder:
C:\Documents and Settings\<username>\Local Settings\Application Data\Apple Computer\Safari
Local Settings is usually hidden, so you will have to change your settings in My Computer (Tools -> Folder Options -> View -> Show hidden files and folders)
Add the following lines at the end of the font list that is already there:
<key>Verdana</key>
<string>C:\WINDOWS\Fonts\verdana.ttf</string>
<key>Verdana Bold</key>
<string>C:\WINDOWS\Fonts\verdanab.ttf</string>
<key>Verdana Italic</key>
<string>C:\WINDOWS\Fonts\verdanai.ttf</string>
<key>Verdana Bold Italic</key>
<string>C:\WINDOWS\Fonts\verdanaz.ttf</string>
Save the file (I did make a backup of it before I changed the file, just in case). Obviously this is only for Verdana; if you have others that are missing, add them in the same manner.
I also marked the file as read-only - it was mentioned elsewhere - not sure if that was required or not. It can be marked read-only under the file Properties.
Windows XP
Windows XP