I would put your mnemonics (stories or other means of remembering the form of the character) into the process earlier. That might allow you to eliminate some of the Chinese time-honored repetitive writing! The more stories – and the dumber or more exaggerated they are – you have about the characters, the easier it will be for you to recall them.
Try using more audio or kinesthetic input, depending on what tends to work better for you personally. That is, you might “tell” yourself out loud what shapes make up the character as you write it: “OK, first I put the sun on top, then the horizon line, then the weird legs” if you’re writing “zui4” [most] for example. (OK, bad example but I’m not thinking today, it’s Sunday!) For kinesthetics, try actually moving your body, arm or hand while writing or thinking about the character. Muscle memory is a very powerful aid to memorizing words.
I used to practice with those “magic slates” kids draw with – you know, th ones where you pull up on sheet to erase it? You could even draw boxes on the top plastic sheet with a permanent marker if you wanted to. Or you could be very modern and get a nice little white board. I always kind of liked writing on those pads with squares ruled on them, even if it didn’t really help me [personally] learn that much. It was just kinda neat.
I also have a nice game – don’t know what it’s called – but it has lots of characters sliced in two (top/bottom and left/right versions of the game separate). You play variations of dominos or similar games with the set. I got this about 10 years ago and have never seen it since, but if you come across more please let me know. Chinese people loved to play this game with us and there were endless good-natured arguments about “that character doesn’t exist” and stuff like that.
I’ve also used a combination of flash cards and writing – get a computer program or one for Palm and that will make the prompts more random and will have them focus on the ones you really need to repeat.
If you want to reinforce tones, you can even practice writing in 4 colors, using the appropriate colored marker to write the character you’re practicing. Again this keys in visual memory for tones, although you’re not working specifically on tones when you write. It all helps.
Not to be a devil’s advocate – but do you really need to be able to write characters by hand? Aside from, say, filling out forms, is there going to be a time when you need to do this without a dictionary and without a computer? [evil statement follows:] Just becuase your teacher says you have to doesn’t mean it is useful for you, and as an adult learner you have the responsibility to think carefully about these issues (particularly because teachers here usually do not.)
If it doesn’t look like there will be that need for you, I’d advise you to concentrate on recognition instead of production. You’ll be able to learn a lot more characters in that case, and will be more fluent reading – which might encourage you to read more, which will improve everything about your Chinese.