I am starting an adventure in a custom setting that may end up as a campaign, depending on popularity. However, part of what makes the setting unique is that magic is illegal and severely punished by all governments (even the local sheriff will get a bunch of villagers to run off a suspected magic-user), due to a past mage war that left behind lots of deserts and wastelands and killed many people. I don't want to change this background, and I want to keep the flavour of magic being seen generally as evil by nearly everyone, but I don't want to limit magic-using PCs too much. A slight disadvantage is acceptable, but I don't want the class to be near-useless due to the repercussions of using magic.
How can I re-balance this?