we have very limited space (4Mb) to put the patch content in
Really? Has Microsoft never updated their limits, or do they figure people with dial-up are not used to waiting? They certainly don't mind 100MB+ game trailers and 1GB+ demos.
I recently downloaded the demo for a 16MB or so arcade game, and there was a 17BM 'update' before I could even try it...