The documentation says that it should be using vagrant@localhost, though I don't know if Drupal would like that any better. Should I try the develop branch on a fresh clone?
Yeah, vagrant+site@localhost is definitely invalid. I guess people have been changing it manually or not actually testing the example project (which is understandable). I propose it be changed to email@example.com. If this sounds good, I will send a pull request.
Looks like this is a bit subjective and might be upstream or related to PHP version: http://drupal.org/node/1478656
Hmm. I think #79 (comment) is still the way to go, although local mail routing may need to be set up for example.dev in addition to localhost, and I don't know how that'd work.