Where is a video stored after it is deleted from my iPhone?
The video is then stored in your Messages application as opposed to your photo library. If you have iCloud enabled for messages it is stored in iCloud as well for both people, since you both have the message.

To see photos stored in Messages, go to [Settings] -> General -> iPhone Storage -> Messages, there you will find a section for Photos and Videos: