I completely agree. Just being a full time dispatcher, I felt the need to correct some information.
I am lucky, I live in a fairly suburban county, with good addressing and good infrastructure. However, I grew up in the boondocks of Missouri, so I can empathize with your problem.
Do you have major events or festivals in your area? Your idea for magnets is a good one, I would corrdinate with other agencies in your county (all PD, Fire, and EMS districts) and even try to get corprate sponsors, to help defray the costs of the materials. Figure out the # of households in your county (available by census data) get a couple of sponsors on board to place their logo on a 3x5 magnet with the information, and do a mass mailing of them. With the sponsors you could cut down on much, or even all of the cost. You might check into it, but they may even be able to work that in as a tax write off for their company.
EDIT: I just saw you are from Canadia. But I am sure there are still aspects of this that will work for you, and this idea is good for anyone in the US as well. Just make sure my name is on the magnets.