Solution:
The last time that I restored my phone as "new phone" I realized that the phone have few of my old settings on it, weird right?
From that I understood that iTunes holds a settings file/files that being installed on the phone while restoring, probably the bluetooth configuration file is being installed as well (my iPhone 3Gs file)
So I created a new user on my Mac, started iTunes (Fresh iTunes Library) and then restores my iPhone to factory settings.
Then I loged-in back to my regular Mac User Account and synced my Apps, Music, Books.... Again. (Did not restore, just reinstall)
YES.. I lost all of my Apps Data, Text MSG's, Settings... But now it looks like my Bluetooth problems disappeared, I have no problem for the last 2 days.
I will keep you posted.
If you have any questions for me I will gladly answer them, just go to my site
coolgeex.com and use the contact form