Why does deleting a node ALSO invoke hook_node_update?
Thanks for your answers, much appreciated!

I finally managed to find the cause. The "problem" is caused by the module https://www.drupal.org/project/field_collection. My node has a field that is a field_collection, and apparently, when deleting a node, the field_collection items are first deleted from the node, which is then saved (which causes the update hook to fire), and only then the node itself is actually deleted. 

It's pretty easy to workaround this issue once you actually KNOW what is causing it, in my case I modified the update hook to check for field_collection items in the node, if there were none it means the node is about to be deleted...