From the FAQs section of the security advisory cited above:
Q: Am I vulnerable if I have a custom logging module that redirects to an error page instead of using the workaround listed below? A: If the responses that are sent out from your custom logging module do not let the client distinguish between error responses either through its content or time that it takes to serve out, then such a module is an adequate replacement for the customErrors workaround. These responses include both the entire HTTP response and the HTTP error code. If any of the above is not true at all times, then this is not sufficient.
This *seems* to indicate that it is necessary to make the entire error response generic, so that different types of errors cannot be distinguished in an way by HTTP clients. In typical fashion, the wording in this Advisory is just not explicit enough to be absolutely sure -- They state what is insufficient, but not what is sufficient.
But by adding up all the clues in this Advisory, I would interpret it to mean that everything about all error responses should be entirely generic, to include the server status response code, the content-body of the response, and even the time typically taken to generate that response. Note that they even recommend inserting a random delay if some of your error-types typically take longer than others to detect and process.
My gut feeling on this is that you'd be better off returning a generic 400-Bad Request, which is the most-generic of error codes indicating a client error if your site typically experiences many client errors (based on the counts of 400, 403, 404, and 410 errors that you see in your error log daily) and very few actual server-side errors. In this case, indicating a client-side error for all errors is "true more often" than indicating a server-side error by using a 500-Server Error response.
However, it does seem to me to be preferable in either case to return the most-generic error code -- i.e. either 400 or 500, so that the server does not indicate any specific "reason" but rather a generic one.
But in either case, returning inaccurate server responses is likely to cause some kind of upset to search engine spiders, and all we can do is to hope that MS fixes the root problem as quickly as possible so that this work-around will no longer be necessary.