Ok, here is the solution to a problem that has very little online about how to solve it.
If you are receiving the "mbstring cannot be found" error, you will need to find you *real* php.ini (phpinfo() will get you that information), and under the extensions listing, php_mbstring.dll MUST be loaded BEFORE php_mailparse.dll.
That's it! What is happening is that the mailparse.dll is loading first, which is (apparently) at least looking for the mbstring library, which it can't find, as PHP doesn't know about it yet. Just remove the old php_mbstring.dll line and move it under php_mailparse.dll.
To find the problem, I commented out all extensions in the php.ini file and then one-by-one reloaded them in until I began receiving the error again (at mailparse.dll). Then, once I moved the mbstring line above, it stopped throwing the error.
An interesting aside, now that the error is not displaying, I cannot reproduce the error (if I comment out or move the mbstring line again). I can't tell you why not, but maybe this has something to do with why some folks don't seem to get the error in the first place.
Hopefully, this error will be addressed in future updates/releases (unless it already has and I just have an old installation).