When I choose to delete an e-mail on my 8100 Blackberry Pearl, it has the option to delete on my mailbox AND handheld. When I click that option, I expect for that e-mail to be deleted in both my handheld AND my gmail account. HOWEVER, it is not. How do I fix this?

With gmail, that very definately should work.

You can try deleting your service books, and going to the Tmo BIS website where you setup your mail (or on your BB) and clicking to Service Book > Send Service books, and see if that corrects the behavior.

Otherwise, give it some time. GMail could just be acting weird right now, I have had a problem receiving gmail today.