I've never used Crayola Washable markers on a battlemat so I haven't had to deal with this personally, but I have a kid so I'm familiar with a particular resource you might find useful – Crayola has a FAQ of tips for cleaning their products off of materials they weren't meant to be used on. The closest I could find for this situation is for Crayola Washable Markers on vinyl flooring (no wax):
Blot stain with a damp sponge, changing the sponge as it picks up stain. If any stain remains, apply alcohol to a cotton ball and blot. If stain persists, apply alcohol to a cotton ball and place on the stain with a weight on the cotton ball. Cover with a glass jar or equivalent to keep the cotton ball moist overnight. If stain is still noticeable, apply Spot Shot as recommended on the container.Special NoteDo not leave Spot Shot on for more than 8 hours. Check after 4 hours.
It's worth reading the whole page instead of just that excerpt, since it has a bunch of caveats like
Before attempting the stain removal method, test each procedure on an inconspicuous area of the material or surface to be cleaned.
… that are worth reading before attempting to use rubbing alcohol on your battle mat.
As you've discovered, battle mats aren't really made for extended marking. Mats are typically wiped after every session, and most gamers use only non-permanent overhead projector markers on them. Even then, some colours (like red) can leave a faint stain even when promptly wiped up at the end of the session.
Leaving a map set up for long periods of time is useful though. For extended marking, you're better off using something different like a large-format sheet of paper or one of the various "gaming paper" brands that are trendy lately. There is an excellent review of your battle-map material options on Wired that lays out each of their strengths and weaknesses: RPG Battle Maps Square Off: Paper or Gaming Paper?. And as a completely different solution, map tiles are a nice trade-off between flexibility and permanence, allowing you to rearrange them into various forms, at the expense of repetition and needing to collect/print/create a variety of them for different shapes and places.