vBulletin and FUDForum have very similar functionality and are both implemented as PHP. The main differences are outlined below. More detailed comparison would require trying them both.
Open Source vs Commercial
FUDForum is an open-source product which is well supported with frequent releases and attention to details/quality. vBulletin is commercial (but relatively cheap). vBulletin is a "visible source" commercial product. Who exactly develops it is unclear "Our team is all over the world. Our headquarters are located in Southern California. vBulletin Solutions, Inc is a company registered in California, US and a division of Internet Brands."
I am less convinced than Imre that commercial support is necessarily better than open source, at least I think everyone could agree that the best open-source products are better than the worse commercially supported products, so comparisons should be made on a case-by-case basis.
Databases
FUDForum works with many databases, while vBulletin only works with MySQL.
WYSIWYG
FUDForum does not support WYSIWYG editing. This does not appear to be a priority for the developers, although there are some pointers to how to add this functionality yourself.
http://fudforum.org/forum/index.php?t=msg&goto=162516&
Bi-directonal e-mail support
I saw no indication that vBulletin support this functionality, in fact some indication it does not:
http://www.vbulletin.com/forum/showthread.php?300725-Mailing-List-integration
Again there are some hints that this can be added yourself:
http://www.vbulletin.org/forum/showthread.php?t=151222&highlight=mailing+list
Integration with common identity stores.
FudForum has a PHP "hook" for integration with other login systems. We would need to look at this in more detail to understand how easy it is to use: http://cvs.prohost.org/index.php/Login_integration
I am not sure what integration vBulletin provides. There appears to be discussion of an LDAP plugin but it is not clear what level of support this has?
http://www.vbulletin.org/forum/showthread.php?t=231909
Ability to block external search engines
I don't really understand this one. Would being able to include a robots.txt at the root satisfy the requirement?
Messages go to database
FUDForum supports this, although it is not recommended "for performance reasons". It is unclear without testing whether there is a significant performance hit.
Importing from other systems
Perhaps there is an FUDForum->vBulletin importer. On the other hand the links in this post all appear to be broken (commercial support at work?).
http://www.vbulletin.com/forum/showthread.php?151319-FUDForum-Import
There appears to be a script for vBulletin->FUDForum. Unclear if it works: