Yes, most likely your IPs are disassociated/removed before the instance shuts down, making any attempt to reach the Chef server from the instance futile. You can always check your cloudformation action logs but disassociating the IP address before shutdown is what makes most sense.
I think some of the workaround are:
Build an app on top of your cloudformation creation so that every time you delete a stack it also deletes the node(s) you want from your chef server. This would a full blown application with a database to keep track of the servers/stacks running. This will require your app to call the chef server API or simply call a system
knife
command.Run your clean up script from another instance running knife/chef-client. You can have some sort of cron/periodic job checking for stacks/servers that have been deleting on AWS and then run the appropriate knife command to delete the server from. This in essence very similar to 1. with just the difference that you don't necessarily have to build a full blown.application.
Hope it helps.