The custom AccessDenied page is showing the wrong page. Basicaly we were missing the request access link on our accessdenied page. First things to check is that the outgoing email settings are enabled and if the site settings allow the user to request access. All those things were set correctly, so it had to be something different (either bad coding or something else). As the custom layouts page was working properly (by going directly to the url _layouts/mycustompages/accessdenied.aspx) it had to be the mapping of the custom layouts page. This mapping in this project is done through a web application scoped feature, but you can check the mapping using Powershell (or modify the mapping).
To check if your custom layouts page is mapped correctly, use Get-SPCustomLayoutsPage (http://technet.microsoft.com/en-us/library/ff607821.aspx). The specific command I used was:
$web = Get-SPWebApplication http://www.contoso.com
Get-SPCustomLayoutsPage -Identity AccessDenied -WebApplication $web | Format-List
Strangely enough, this was showing that the AccessDenied page was mapped to _layouts/mycustompages/accessdenied.aspx which is correct. Just to make sure I reapplied the custom layoutspage through PowerShell by making use of Set-SPCustomLayoutsPage (http://technet.microsoft.com/en-us/library/ff607768.aspx) and the old page was still showing.
Cause and Solution:
The custom access denied page was being cached. After doing an IISRESET on every Web Frontend everything worked fine.