Look for any drawing software and not specific evac stuff. I had a look at Smart Draw it seems to have the basics for doing floor plans with icons for fire ext and hoses, plus there are heaps of other functions for planning and presenting so it can be used for other functions outside of just drawing. There is also eziblueprint http://www.ezblueprint.com/examples.html this seems to have icons for evacuations as well.
Or if you just want to use word or publisher to draw basic evac plans you can get extingusher icons and other stuff from clker. Free open source clip art at http://www.clker.com/clipart-2702.html.
I have not tried any of these so cannot advise. Hope it goes well.
PS. Keep us posted on how it works out and maybe you can recommend something when you find it.
PPS. I have used MS visio in the past. Vision has evac symbols and functions for inserting the legend, you can also import symbols. I just found an old pan for a site built on visio and rememebered this was not the most enjoyable experience, a bit clunky to use. I am thinking of trialing the ezi blurpint program, looks simple enough, not sure how it will go for doing full site maps with roadways and buildings.