1) Sure you could delete the existing site pages, delete the ps4 tables and then reinstall 4.01.
2) If you are doing a clean install of PS4.01, meaning running the install wizard, you do not need to run the update script.
3) Yes, the 4.01 update includes SEO optimizations.
4) Perhaps there is an issue with session management on the server. try the session test file from this post:
showpost.php?p=23826&postcount=2