Would it be possible to simply make the device lie about the support to the server? It seems to me that the ideal behaviour for the user would be to promise Exchange anything it asks for, then just do what the user tells it regardless.
Without implementation of provisioning feature - no. It definately will not tell to Exchange server that it is provisionable if it is not. This is simply illegal.