Another vote for Oxy and sunlight over the period of a week or two here. I've dealt with what you're describing and a Mr Clean eraser pad is great for dolly cleanup but won't remove marker or staining. Some stains just never come off though, even with OXY, and a trip to the doll hospital is needed.
On the plus side, she'll come back in a cute little hospital gown w/ID bracelet & balloon which most girls really enjoy having and isn't sold seperately. Since it's a newly purchased doll, it's possible they'd do it without charge. I'd call or send a note asking about the possibility. Also, if you can drop it off at an AGPlace store, or know someone who can, AGP will send it in for you and you won't need to pay postage to get it to the doll hospital in WI.
I don't remember reading what doll you have but AG had a known problem with Ivy's pants staining the legs over the past few years. Most of the Ivy doll meet outfits have been revised to a slightly different fabric now to eliminate the issue. They've been repairing affected dolls at no charge and replacing the original outfits with the revised one.
Almost forgot... Whatever you do, don't use fingernail polish remover or paint thinner. They'll damge the vinyl and usually don't work anyway. If you've ever seen one of those dolls with yellow/orange looking fingertips, that's what caused it...
