I've played through the game once and would like to play again, I've tried 'verify/repair' (which worked on Armada 1) and uninstalled then reinstalled, but it's still showing all the missions as completed....

Delete the file "shell.set" in the \save folder, for example:

C:\Program Files (x86)\GOG Galaxy\Games\Star Trek Armada II\save