Thanks to @Austin (http://apple.stackexchange.com/users/5916/austin) and others, I finally solved the problem! I thought damn it, this is a Unix box, i should be able to find out what's going on! I found another Snow Leopard machine at work which never had Internet Sharing turned on and in a terminal I ran:
touch now && sudo find -x / -newer now
and I got a short list of files that always show up (spotlight indexes, log files in /private/log and if you are using file vault a bunch of encrypted sparse bundles ...)
then I enabled Internet sharing and this time I ran:
sudo find -x / -newer now
obviously without the "touch now".
It turns out that other than a bunch of log files and other junk there are a hand full of files that are modified.
I copied them all over to my machine and modified the interface names and few other hostname and ip addresses and stuff like that.
The problem happend with
/Library/Preferences/SystemConfiguration/com.apple.nat.plist there is a primary service key there which is set to a UUID and it is different on every machine that I tested (2 machines actually) and it does not work from if you just copy it from one machin to next.
* IF YOU ARE IN A HURRY JUST READ THIS PART *
From the start I avoided reinstalling my OS because I had so many Installations and configurations that I didn't want to loose. It turned out that if you use the original DVD that comes with your machine and reinstall your OS ALL YOUR APPLICATIONS, HOME DIRECTORY, custom modifications, mac ports and fink installations, preferences, network mounts, network locations, developer tools, ALL ARE PRESERVED. BUT IT REINSTALLS THE CORE SYSTEM COMPONENTS that fiex my preferences sharing pane!