Very interesting discussion. I think something that (understandably, as your thesis here is narrow) should be considered is how ethical theories outside of utilitarianism and deontology should be considered. Although you provided a fairly strong argument against deontology, there was no argument for uniquely utilitarianism as many of the intuition you had against deontology could also apply to most other ethical theories. Perhaps a virtue ethical, care ethical, or communitarian approach could accommodate for the short comings of deontology as well as (or maybe better than!) utilitarianism. 

Thank you for the post!