First off, you can upload your vbm file to
http://dehacked.2y.net/microstorage.php if you'd like as well... that way critiquing the run will be easier as with avi's it's pretty much guesswork.
Overall I think it looks good for a first attempt. The first level appears to be fairly trivial from a route-planning perspective as it requires no backtracking. You already mentioned level 3 so I won't bug you about that :) Level 2 seems like it could be improved by getting that top row of dots earlier on so you don't have to backtrack as much at the end. 4 & 5 looks good superficially to me, though I would bet there are improvements to be made...
I don't know if you've seen the thread on the NES version which was for just the first level, but Randil managed to squeeze quite a few frames out of it after several revisions:
http://tasvideos.org/forum/viewtopic.php?t=5431&highlight=
One other thing: why give yourself the maximum number of lives? This seems to contradict your choosing the hardest difficulty...