Sounds like RAM is the problem not internal storage.  Android is basically killing the launcher to recover memory and is usually most notable if you're doing something in landscape.  Believe the 3rd party launchers like ADW and Launcher Pro have an option to keep the launcher in memory.  There should also be an option to turn off rotation for the launcher which should help.