You should certainly be able to do this, but I'm not sure on the specifics unfortunately. Did your old invoice layout do this before you applied my changes? The new one should still be able to as the code changes are only visual.
Under Management > Taxing System, have you checked 'Enable tax exemption for customers'? This would be your first point of call.
The lines for the tax display are in order_data.tpl, starting around line 38.
You should be able to add this somewhere:
{if $_userinfo.tax_exempt eq "Y"}
<p>Note: This order is tax exempt</p>
{/if}
This will display the message if they are tax exempt.
Cheers,