When you really learn the kanji (or Han characters to be more generic, kanji being the Japanese name), you end seeing them with their components, and you'll be using your left brain to write them - just like when writing English.
As for left-brain/right-brain, I doubt that's a useful distinction here (if indeed it's useful anywhere). But that aside, I don't think it's correct to suggest that native speakers process Han characters just like English. See for example: http://brain.oxfordjournals.org/content/123/5/954.full.pdf
I get the complexity is quite high since every symbol will look different depending on what's after and before it however you would think you get enough practice taking note or is this a formal language used only in certain contexts?
For me at least, that's approximately what it feels like to be unable to remember how to write a kanji.