cjrgreen: Sleeping on one's rights is not the same thing as giving permission. You can wake up and invoke those rights at any time. That said, few companies are going to have much of a problem with free fan-made works. Just don't try it with the IP of the known pit bulls of the industry, like Nintendo, Sony, Lucas Arts, etc.
"Fair use" ('fair dealing" in the UK and Commonwealth) is, you are right, a principle that applies only in common-law countries. Many other countries have far stricter limitations on conditions under which you can make a derivative work that might infringe a copyright.
It makes a difference if company knows about fan game or not. If they know, and tolerate, then it may be considered as a permission, even though it's not an explicit one. Of course it's a question how someone would proove that company knew about fan game, but I guess someone could just show that it was well known in the Internet.
Of course, they (IP holders) can change their mind, but that would be revoking permission, not the lack of permission "from the beginning".
And as some countries have far stricter limitations, some other countries have them less strict (and still fit into international IP law conventions, I'm not referring to those countries that allow breaking IP law).
Navagon: In that case it exists in a grey area. Nothing would stop them from bringing the hammer down at any time.
It's not grey area, it's just the permission which can be revoked any time.
---
Anyway, the only thing that one may expect from IP holder in case of fan game is the Cease and desist letter. Companies make money, and they got their money from fan. Suing your own fan = less money. So I think it's nothing to worry about, as long as you don't get profits from fan game.