Android (the one direct from Google) doesn't support ActiveSyncForExchange.
However manufacturers can add their own code and applications to the phone they sell.
HTC added an ActiveSyncForExchange compatible application in the Magic.
But this app doesn't work against ZCS.
HTC's new phone, the Hero also has such an app.
This time it seems to work against ZCS.
Bug 38854 - Support for HTC Magic (Running Android OS with ActiveSync support)
So now you should turn back to HTC and ask for an updated firmware with the updated app...
It seems last firmware for Magic fixes the issue.