How could I recreate this stroke effect in After Effects and/or Sony Vegas? In the many Red Dead Redemption trailers, they use this cool effect were paint/brush strokes somewhat pan into the actual game-play and overlay it with an awesome drawn out piece from the previous frame - what I am trying to do, is recreate just that.

An example is : 
                
             at 0:11 and 0:17
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.