I have never had a wasteland cleared, ever, in any version of FE.
Oh I killed the elemental lords and every single army in their zone but it never completed the "Kill X" quest... I did however get the trophy in my capital like you did whenever I slew one.
Which was rare because often they did disappear and I know the AI didn't kill them.
Sometimes when everyone died their ZoC disappeared but the land did not change...
If it was meant to be retain the unique look (crystals and the like) but merely become "fertile" then the issue is that elemental lord ZoC turns lands fertile the same as a player's ZoC so their lands are always fertile to begin with (and make excellent colony spots...)