I have shot around 10mins of green screen HDV 720p footage (for a 2min greenscreened short). I use AE CS4 and PProCS4 (with Dyn Link)

*When* do I key out the greenscreen & do the compositing?

Option A:
1) Assemble a rough cut in Premiere pro (basically delete all unusable takes)
2) Right Click and Replace with AE Composition (do I need to do this for each clip or the whole sequence?)
3) Do the Keying & all complex compositing in AE and come back to PPro to apply transisions etc.
4) Render out to Adobe Media Encoder for FLV (online distribution)

Or Option B:
1) Start in AE, throw away usable takes
2) Key and do composting in AE
3) Render to xxx (which format??)
4) Import to PPro and do the fine tuning there?

I would choose option A, since that makes the composition in AE easier to handle and the simple work can be done in PR.

The first one is the best. I just completed an 800 shot greeenscreen project with that workflow. One thing to keep in mind is you need lots of RAM if large project. If you are using 4gigs of ram you might run into crashing issues. CS4 runs AE in the background about 3-4 times while using dynamic link. You use up the ram really fast. If using 64bit system it can allocate 4gig ram to each program open. Hope this helps

That explains why I see 'AfterFX.exe' multiple times in my TaskManager... Unfortunately, I just have 2 GB ram, and system crawls...

To speed things up - should I split sequences into its own projects? (is it even doable?)

To speed things up and improve stability at the same time, get extra memory.