Thanks for all the answer, I knew someone will help me. Now, I'm digging trough the theme files and searching for the damned 404 code. I hope I won't mess things up.
If this thread continues, you will continue to have "experts" tell you you can or or can't have Adsense on 404s and this will end up being a worthless thread. Basically, put, here is a definite answer to this question - http://forums.digitalpoint.com/showpost.php?p=1300826&postcount=60 Now someone lock this thread before we have another peon grace us with their thoughts.
I'm sorry but you would believe a person with a post count of 170 to post truthful emails from adsense? That could have been modified to say whatever he wants. Read googles publishers TOS, it clearly states NO 404 PAGES!
Actually in this case I would. The poster, Michau is known to me from outside of DP. If there is one thing I know about him, it is that he does clarify with the Adsense team a lot (He writes a lot of site scripts which use Adsense). If it was someone else, I would have had the same doubt as you. Note, the email he was sent by the Adsense team was quite specific about in which context Adsense is allowed on a 404 page. The only way to discredit him would be to quote the email he was given and send it to the Adsense Team yourself to verify.
But still second hand to everyone but him. In matters like this, second hand information does not suffice for me and I look to the TOS/Policies themselves, or I talk to my Google friends. They may say the same thing as what Michau posted, but now it's FIRST hand, and that I will accept.
If you read Michau's post, he actually has the ticket id's from his queries to the Adsense Team. All you need to do is to send a query email with those ticket numbers to verify the answer. As it stands, the response makes sense in that your normal 404 pages are not allowed to have adsense ads on them but 404 pages with content is. Again, you have all the information to prove/disprove Michau's email response. Anything you come up with from the Adsense Team, will be questioned in the future by other posters anyway and so the cycle will continue.
Anyway, I managed to remove the ads from the 404 pages so, this debate can be shut down. The safest thing to do is not have them on 404 pages dot.