Mawile is also available in the wastelands only, so i'm guessing you'd better catch some other stuff for now ^^
On the topic of Leftovers: Leftovers is one of the best items in the game... Granted, it's not going to "decide" a battle against gym leaders that use even better items that you can use, but still... Ame doesn't want us to be on par with the gym leaders/rival/team meteor, on the contrary: She wants us to die while playing Reborn, and anything related to that...
Although i know better now: ALWAYS bring a pokemon with Thief against a gym leader... I don't have a focus sash, a rocky helmet and other items for no reason, you know ^^...