Um, there is one rather big hole in your observation: all of the above titles are merely the translated versions, with the Japanese original often being totally different!
The original titles are as follows:

• Alita: Gunm - doesn't follow the convention at all
• Nadesico: Yuugeki Uchuu Senkan Nadeshiko - translates to "Raider Space Warship Nadeshiko", fits not very well into the pattern.
• Utena: Shoujo Kakumei Utena - the English title is literally translated, but the word order is different.
• Miyu: Kyuuketsuki Miyu, just "Vampire Miyu"