I remember doing a competition (puzzle based) like 1,5 years ago, where I wanted to use item frames for a puzzle. Turned out, that the 'act' of rotating/removing/adding items in/from/to frames is just the plot switch perm. So, basically, when I had plot set perm switch on for stuff like buttons and levers, players could also remove items from my item frames even though the intention was only for them to be able to rotate them.
ANYWAYS!
Are you sure, that the plot you were on, had the Switch perm set to Off? If not, let him try that.
Otherwise it's a bug.
EDIT: Right, sorry. Didn't really watch your second video. I just saw you doing /plot perm, which said that all the perms are set ON for friends. Meaning: if you have the guy added to your friends list, it's normal for you to remove things from the frames.
Well, let him try setting switch to OFF for everyone anyways, if that doesn't work a tech will have to look at it.