I bought an iPhone 3GS from Australia. It's factory unlocked.
I got it to Lebanon where I put my SIM Card in it and iTunes unlocked it. I got the screen that says the phone is unlocked and all. But now it's not activating. Could it be that my carrier isn't supported yet?

Moreover, I want to repeat the whole activation thing. How can I do that?
ie: I want to go back to when I first got the phone out of the box - before plugging it in the computer for the first time.

DO a hard reboot (hold power + home till Iphone reboots).

Just turn on/off airplane mode you should get signal or reset network.

Once factory unlocked phone connected to Itunes it will automatically gets unlocked whatever SIM you put ...

secondly you are referring as 'box packed' thing ... just connect to Itunes and select restore (select downloaded FW... )

Yes you should try rebooting. Network should be also reset. Don't worry about carrier. As it is unlocked that means it is jailbroken. So you can use use it under any GSM provider.