I do not prefer marked queens... of course, for research, they have to be positively identified... so for that purpose I prefer marking them with numbered disks as opposed to paint... some levels of hygienics will cause the bees to become obsessed with removing that color... if its paint, they can damage the queen, if its a disk, they simply pick at the disk almost like scratching a helmet instead of a head... the obsessive picking can reduce the queens performance at the least and kill her in the worst case scenario... so when I want to see what someone's stock is capable of in my operation, I request specifically NOT to mark her... however, this type of occurrence is rare and it seems that you had a constant issue with it... the mark problem may actually just be a side issue and the de-throning may be more of an issue of genetic conflict instead... can you describe the bees that were originally in the trap out and what type of bees are kept near that location, as well as what type of queen you were using to requeen with? The original queen could have had her abdomen squeezed a bit during marking... that would cause supersedure, then the next queens could have been of conflicting genetics... assuming that they were from a quality producer, so handling wouldn't be an issue...