While I know the fighters (or used to know them, it's been awhile) inside and out, I couldn't get into story mode outside of IaMP. Opponents with super armor = combos become impossible = screw this.
Basically what I'm saying is, I can't really help with story mode, because characters that are good outside of it could be useless in it, and vice versa. Generally speaking, I remember Reimu's, Marisa's, and Sakuya's scenarios all being beatable with 236C abuse, and remember Reisen's being easiest due to it only being three stages long.