Based on the mixed results from different browsers using similar settings I'm wondering if you have some security software in place that may be preventing the session cookies from being written. Do you have any tools installed that may be dealing with browser security?
In FireFox you can view cookies that have been set from options > privacy > delete individual cookies. In here you should be able to find the host and take a look for the cookie, there should be a PHPSESSID cookie that has a value. Other than this identifier the other session values should be stored server side.
