OSX users went through this teething pain of supporting Gmail All Mail 2 years ago:
How To Make Gmail and OS X Mavericks Play Well Together - The Mac Observer TidBITS: Mail in Mavericks Changes the Gmail Equation
Gee, I wonder why people have worse performance problems than others... This should be looked into.
"All Mail" wasn't supported prior to that update and had to be disabled after support was added officially by Apple. After the update, you HAD to enable it. Apple didn't do it automatically, nor informed people and made the transition painful. I think the numbers might be inverse for BlackBerry's transition of All Mail handling than Apple's (hehe).
I'll repeat. This is intentional hassle added on Gmail's part to keep users on the Google ecosystem. Their service depends on you coming to their web interface to use their product and use Android! Labeling on their system helps storage space for Google, they only store one copy. Everyone else following imap duplicates space, unless a kludge is implemented to track the duplicates, which uses memory and cpu to track. There shouldn't be 100% anger at BlackBerry for something Google caused full knowingly they were going to break clients and doesn't work with the competition to ensure a smooth experience. It looks like Apple had to reverse engineer their kludge implementation themselves, and took them years to implement to a less than stellar release.