How could I recreate this stroke effect in After Effects and/or Sony Vegas?
It's a lot of matte painting.  While the video is still running, they animate a semi-transparent shape (probably made in Illustrator or something similar) and animate the shape in over it.  As soon as the painting finishes, they switch to a frozen shot of the last frame and seem to transition to the painted version of that frame.  It's hard to tell exactly from the Youtube video since I can't frame advance, but that should get the general feel of it.