Vbulletin with the vbSEO plugin. That is the best forum software to use which is the most search engine friendly. You'll have your pages indexed in a few hours typically.

vBulletin - Instant Community (non affiliate link)
vBulletin SEO by vBSEO (affiliate link)
or
vBulletin SEO by vBSEO (non affiliate link) Both take you to the same page.

I don't know any that are search engine friendly. Most freebies claim they are, but if you want to be search engine friendly and keyword friendly, vbulletin with vbseo is the way to go becasue the use includes the topics title in the URL and the meta tags are structured properly and are keyword rich. Other forums use strings such as viewtopic=?983744y8734 to display a forum topic and don't use the same meta tag for all your forum topics. So you have to rely solely on your page's content to be search engine friendly and well, usually that's not enough.

PHPBB3 is better than VB, easier to manage, VB forums have far too many confusing settings, plus they get spammed a lot too, phpbb3 ones dont.

there's a phpbb3 seo plugin that you can use that rewrites the urls, like the vbseo one.

No offense intended, but if phpbb3 was indeed better, you think warriorforum.com would have gone with vbulletin and vbSEO over phpbb3? phpbb3 is indeed a good free solution, where vbulletin is a professional paid solution. phpbb3 is very popular because it is a good free forum that many people don't wish to invest in something better. When phpbb2 was around I lost a server due to the worm vulnerability it had. From my past experienced, I stay away from anything related to phpbb. vBulletin is my joy and have gotten great results from it. Also, vbSEO, is not just about URL rewriting. Check up on vbSEO to learn what it does. Ultimately, it's star480 to decide what he likes best. From the many years of trying forums left and right, for me, vBulletin is simply the best and the vbSEO plugin is the icing on the cake. Just my opinion.

As for spam, get a recaptcha key and activate it in vbulletin and you're set.

Free forum software:

SMF 1.1.8
Home of SMF: Free PHP and MySQL forum software

with SEO4SMF:

Webmaster's Talks ! - Downloads

I go with vBulletin + vbseo

and suggest it to all my clients
It's what I use on vBulletinSetup and TransformTopeka

smf is something i would look at

I use PHPBB and it's pretty good. Although I don't like how difficult it is to change the templates some times.

If you wanna know which pages have "follow" on their outbound links, try the SEO Tool for Firefox. You just simply turn it on and off as required by the click of a button.

Great tool!

I fail to see how this post is relevant to the OP post?

You gotta find forums that are do-follow but even better are forums that have actual pagerank on the front page of their individual threads.

I use phpbb3 and so far, i can't complain.

It sure be Vbulletin i think , most webmaster forum use it

You couldn't be farther from the truth.