I use Joomla! 3.0 now, but a few years ago when I had Jomla! 2.5 I had a few problems with invalid token. I would login as user1 on firefox and as another user (user2) on chrome browser. When I logged a user out on one of the browsers, it would give me an invalid token on the other user and browser. Also it would show up every now and then when I did other things, but I don't remember all the issues.

I do not use the Joomla! login page (menu item) . Instead I would use a login module for my home page. And step by step:

1)Using Redj - http://www.selfget.com/downloads/file/24-redj-community-j30.html - a redirect component - I redirect this > =login - and I redirect it to my home page

2)Using Token Interceptor - http://www.joomunited.com/products/token-interceptor - and with this you can display a message other than "Invalid Token"

But that is how I got it to stop, by redirecting> =login (If you use Redj, you must disable the Joomla redirect plugin)

Note: From my understanding the Invalid Token only displays if your cookies are somehow being cleared after you login