I've noticed Firefox browser in my logs, so I installed it.
Today I was fooling around with cookies (CGI::Cookies module), sending, receiving and putting the result into MySQL database.
IE and Netscape worked fine. Then I tried Firefox - every time I accessed my page it would show up as a very first visit. I closed Firefox and opened it several times, I checked everything 20 times, no errors on my side. Firefox wasn't sending me the cookies back.
So I went to the Firefox' options to check if cookies are ON by default. It has a nice cookie browser in it, so I found the cookies I was sending, checked them out, it was the two latest (freshest) cookies. I deleted them. Reopened the browser and hey everything worked! The End.
I believe I can't go back to the state when it doesn't send cookies, but who knew?

P.S. my cookies were just two numbers (2 digits each), and it's the lastest Firefox available.