@b0rk so first the trick, then the reasons for it:
mapfile -t paths < <(<<< "$PATH" tr ':' $'\n' | awk '!seen[$0]++'); printf -v 'PATH' ':%s' "${paths[@]}"; PATH=${PATH:1}
The real trick is that the awk step deduplicates entries _without changing the order of the path elements_, which of course is crucial in this case. The printf/PATH=... step is just about reassembling the array of results back into a string with minimal opportunities for errors to creep in.
1/2