What I'm considering now is low rez diffuse, mostly flat colors for characters, and straight up vertex painting for buildings and props. Thanks for your guys' help.
Thanks Ben, that does work. Will it be impossible to use vertex colors with say, the toon shader? (I think Nintendo did this for Zelda WW) Or am I forced in having a diffuse with the flat coloring/style I want.
There are little touches all over that model that show they used a mostly flat diffuse anyway (boot creases, edges of the tunic, lips, not to mention shield and sword). Wouldn't it be possible to frankenstein a new shader out of the vertex color and cell shading ones?