Today I had been contracted to move a site over to GoDaddy’s servers, The site was Mambo 4.5(1.0.9) but that made no difference as I upgraded them to Joomla 1.0.15
The reason for this blog post is to highligh and publisise (so that others are helped!) the fact that, for some strange reason, GoDaddy requires an extra step in the process to set up SEF Urls in Joomla.
I found the solution over here and the important difference to normal hosts is this bit:
Edit the htaccess.txt file — For Search Engine Friendly (SEF) URLs, you will need to edit the htaccess.txt file to turn on the RewriteBase option. In the file, you will find a line that reads #RewriteBase / that you need to change to RewriteBase / — remove the pound (#) sign.
Hope this helps someone 
This did not solve the issue for me. I use Joomla one point five. Maybe this only works for the older version of Joomla.
You are a genuine man. Your topic has saved me a lot of trouble. Many thanks.
By the way, the website I was working on used Joomla 1.5.15