You did not mention which screen recording programs you used. I use both Camtasia (costs money) and CamStudio (free). Both programs will let you create recorded videos in various formats besides an exe file, that are viewable in Moodle without downloading first. I have been using flash for a few years which makes good quality video without the filesize being too large. For instance, I have one tutorial made with Camtasia I just looked at that is 31 minutes long, has 16 sections, and total size is less than 24MB. The screen quality is excellent for seeing detail and can be zoomed if needed during the editing process.
Both Camtasia and CamStudio record in avi format which can then be edited. You then produce your final version and render into a compressed format such as flash, Quicktime, Windows Media, etc. The version of Camstudio I am using can only do avi and flash. Camtasia can do much, much more and has more formats available for the rendered output.
Hope this helps.