The uniform inconsistency is something I've thought about for years. I never realized the Vulcan officer from Shakaar was from a visiting starship.
I believe each branch of Starfleet determines their uniform.
The security officers in VOY: Non Sequitur were from the security division of The Starfleet Engineering Corps. Jupiter Station is part of Starfleet Science. Voyager itself is from a branch that uses those uniforms.
The security officers from DS9: Homefront and Paradise Lost were either from the U.S.S. Lakota, or the big Starfleet Security. Starfleet Command also uses those uniforms.
The Admiral's Aides are another story and it veers into my head canon. These officers tend to wear the TNG style red uniform no matter what the rest of Starfleet is wearing at the time. They were seen in VOY: Non Sequitur, the one and only time those uniforms were seen in VOY in a non-flashback setting. They were seen several times in DS9 during the grey shoulder era, last seen in DS9: Tears of the Prophets all the way at the end of season six.
I like to believe the red TNG uniforms were the traditional uniform of the Admiral's Aide. I believe they were used for decades before and after that style was widely adopted. I think some sort of uniform emergency caused all of Starfleet to adopt that style for the brief six year period while they figured it out.
That means the color shoulders were probably being used on deep space outposts during the collarless era.
And finally, I can't think of any logical explanation for Star Trek Generations. That movie had a lot of aesthetic inconsistencies.