I start as soon as I catch, receive, hatch, etc. the Pokemon, but that's only because I don't want to remove the unnecessary EVs later on. You can EV train at any level, though. It really doesn't matter when you do it.
STOP CALLING ME HOME ROWED http://i.minus.com/ib1uFDGNC2IrTo.gif
Well it actually a lot quicker EV training at a higher level and you can do easily do so without wasting any EV points. Or at least useful ones. Getting 2 EVs doesn't matter as only 508 of the EVs matter.
I'm not sure exactly but their should be a place where you get high level audinos with only one attack moves (if any).
I usualy stick Toxic and Double Team, and give them a lucky Egg. You can often gets like 35 levels just from having a Lv 1 knocking out a level 50ish audino.