We removed all of the references to the entity, and the entity got deleted. So far no issues. One of the developers on the project created an action which one of the Input Parameters was an Entity Reference to the deleted entity. After the entity was deleted, when the developer tried to open the Action, he got a Query error, and could not open the action. In the Url of the designer we could see that there was an error that said "Entity xyz_customentity does not exist in the metadata cache".
After a little brainstorming, we exported the action (as a solution), and found the Xml of the input parameter that was pointing to the entity. We could remove the Input Parameter Xml and reimport the solution and hope that everything would work, or the probably easier solution was to just recreate the entity (no extra customization needed) and keep the same schema name.
We recreated the entity, and immediately the action opened up. We then went on and removed the Input Parameter that was causing the issue, activated the action and deleted the entity. Quick Fix to an annoying problem.
The bottom line is this this should probably not happen.
I submitted this to ideas.dynamics.com. If anyone is interested in voting up this idea, you can click on the following link: