Fixed!
It turns out that the NodeRef in question points to a group that the user belonged to. I was not able to delete the group through the web client, because of the same issue (Node does not exist). I figured out that Alfresco was getting this fantom NodeRef from the Lucene index, so I attempted to rebuild the lucene index by setting the property "index.recovery.mode=FULL" in my custom-repository.properties. The FullIndexRecoveryComponent completed without a problem, but I still got the same error when I attempted to delete the user or the group in question. I decided to delete the lucene-indexes folder from the alf_data folder, and try the full index recovery again. Presto! It worked. I am now able to delete the user and group in question.