"Searching for Opponents" Issue

You can try to:

Log into Wiimmfi with Brawl
Go here and login(It's the same username and password you have on this board)
User Pages -> Assign a Console
Type in your Brawl FC into the form and click "Assign"

It should show the console's FC in the settings page, along with your Brawl profile.

Also, that's very odd for the address book to have been removed. I mean, it's still there on my Wii U, and I'm not sure if Nintendo could even release an update to change the vWii in any way, shape, or form.