Kendogrid destroy() and recreate the table on a new datasource, why do the old table columns still exist?

Most probably this is because you are not clearing the content inside the Grid container. e.g.

$('#gridName').data().kendoGrid.destroy();
$('#gridName').empty();

or shorter syntax

$('#gridName').kendoGrid('destroy').empty();

Other way the Grid takes into account the old html that is left - do not forget that the Grid could be initialized from table like here.

Just want to clarify on the last bit of Peter Subev's answer because it helped me:

"do not forget that the Grid could be initialized from table like here"

This is just saying that in your HTML you used a <table> tag rather than a <div> tag. Using a <table> tag separates the Grid table data from the Grid columns, so when you do $('#gridName').kendoGrid('destroy').empty() it is only destroying/emptying the table data and not the column information.

Switch your HTML <table> tag to a <div> tag to get the desired result.