We don't know what rules gmail is using to determine the spam. In the link you sent they are citing the section that is titled:

"Similarity to suspicious messages" which is pretty ambiguous. Have you tried emailing a test message from your email program to the same address? Sometimes free email providers flag automated messages as spam.

There are may other possible reasons for them marking it as spam, but the test above will narrow down the scope of the search for the specific reason.

You also might simply disable email verification and use a plugin like Spam-O-Matic for vBulletin to obtain better and more reliable human verification during the vBulletin registration process.