After a bit of comment discussion, I think we've nailed it down.
Permissions trickle down in Sharepoint. You have web application permissions in Central Administration (Application Management -> Policy for web application) to deal with that grant permissions to users globally for the web application.
The next set of permissions down would be site collection owner/site collection administrator. If a user is a SCO/SCA, they'll have access to everything in the site collection whether or not they've been granted permissions.
Then you have site permissions, either by a Sharepoint group or explicitly added.
If you remove John Doe from the web application policy and he is not listed as a SCO/SCA, he will not have access to the document library if his Sharepoint group has been removed from the access list.