Apple Mail is not syncing completely with Gmail account
Rebuild does not show up in the activity window, even when it is doing things in the background. I've experienced this first hand in the past. So, give it some time.

However, rebuilding I think only helps rebuild the index file based on the messages stored on your computer. It does not compare notes with the server, I believe. 

Honestly, I would just remove the account and add it again, so that it downloads your entire account back to your computer. Not an elegant solution, but it has done the trick for me a few times.