Solution:
I got the permalinks to work for Godaddy. I had to add an extra line in .htaccess to make this work. GoDaddy appears to be taking 404 error page over .htaccess and thus was giving errors for all pretty permalink request.
ErrorDocument 404 /index.php
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
The ErrorDocument 404 /index.php line above makes all the difference with GoDaddy. It forces handling of 404 error with that of WordPress index page and works fine.
Hope this helps everyone trying to make pretty permalinks like %postname%
work with Godaddy