Thank you for posting this; I am experiencing the exact same problems.
I have installed the latest WordPress and everything works perfectly except for the Permalinks. Whenever I adjust to anything except for the default, it results in a 404 error. I have tried every fix suggested in the Codex and in dozens of postings about this topic. None work.
The installation did not create a .htaccess file, so I added a blank one. I have set the permissions to allow changes to the file, but when I adjust to a different permalink setting, it seems that nothing is written to the .htaccess file.
I am also using a GoDaddy Windows Virtual Dedicated Server. I have seen postings about problems with GoDaddy and with Windows (instead of Linux), but I need to keep this server because I have other sites running on it.
What else could it possibly be? Are there places where I can speak with someone on the phone or offer access to my site to see if anyone can troubleshoot this? Many thanks.