Page not found - No umbraco document matches the url

Question

When typing in a url that does not exist I want to display a custom 404 page however when I type in a non-existing page I am seeing a Page not found No umbraco document matches the url in the browser

At present I am to running multiple websites in one umbraco v6.2.5 application and there are multiple languages for each website for example the following:

 - www.mydomain.com/en 
 - www.mydomain.com/de
 - www.mydomain.com/fr

The config\404handlers.config consists of the following:

<?xml version="1.0" encoding="utf-8" ?>
<NotFoundHandlers>
  <notFound assembly="umbraco" type="SearchForAlias" />
  <notFound assembly="umbraco" type="SearchForTemplate"/>
  <notFound assembly="umbraco" type="SearchForProfile"/>
  <notFound assembly="uComponents.NotFoundHandlers" type="MultiSitePageNotFoundHandler" />
  <notFound assembly="umbraco" type="handle404"/>
</NotFoundHandlers>

The document type and template have been created and the template has been assigned to the new 404 node but it is still not working.

I can see that the issue is related to the subdomain as when I remove these (i.e en/, de/, fr/) from the culture and hostnames the 404 page starts working but this is required to differentiate between the languages..

Can someone please suggest how I can get the 404 page to work with the subdomains, thanks!