HELP: Custom Screen Screencasts to 720x540

Hi,

I've got a client who has recorded 24 screencasts for me in Storyline.  The problem is they did them as full screen.  I wrongly thought these would render OK when moving to 720x540 (I know crazy assumption!).  They are around twice the required size.  Before I start the long process of re-recording them I wondered if anyone had any ideas.  

I've tried changing the story size using scale to fit but obviously that means I have a third of the screen as white space (and the text is too small to read).  I've also tried saving it as a video, zooming out and recording the screen with camtasia but again the quality wasn't good enough.  

I'm sure I'm stuck but you guys often have an answer crazy questions