The "of" is not redundant in any of your sentences, because you can't remove it without changing the words.
Saying something is "of importance" is another way of saying it is important. You cannot say "of important", so your first example would have to change:
- It is of the utmost importance
- It is the most important.
The same goes for examples 2 and 3:
- those built were of interest = those built were interesting
- cooperation should be of great value = cooperation should be highly valuable
Your final example is slightly different in that "of the highest order" is idiomatically used as a suffix to add weight to something.
- He’s a bigot of the highest order.
You could say "he's highly bigoted" which means the same, but doesn't carry quite the same impact. When used this way, it exaggerates it and makes it insulting.
Some similar examples are idiomatic one way or the other. For example "a person of colour" is considered to be a polite and acceptable term for someone who is not white, while the alternative "a coloured person" is considered to be insulting.