Do ponto de vista sintáctico, ou seja, tendo em conta o tipo de construções em que o verbo ir pode ocorrer, nada de mal há com a expressão «Fui sair». Com efeito, o verbo ir utiliza-se com algumas preposições, sendo as mais frequentes a («Fui ao cinema») e para («Ela foi para o Porto»), com os advérbios bem e mal («Isto vai bem») e com verbos no infinitivo. Analisemos alguns exemplos em que esta última construção ocorre:
(1) Amanhã vou sair.
(2) Hoje vou sair.
(3) Ontem fui sair.
(4) Ontem fui ver um filme.
(5) Fui falar com ele.
(6) Fui fazer aquele trabalho.
(7) Fui concluir a tarefa.
O que distingue as frases (1) e (2) de todas as outras é o facto de as primeiras indicarem uma acção futura, enquanto as restantes se reportam a acções passadas. Se (1) e (2) não oferecem problemas; se as frases (4) a (7) não oferecem problemas, o que acontece com (3), que, efectivamente, parece estranha? Em (1) e (2) o verbo ir funciona como um auxiliar de tempo: a acção designada desencadeia-se no futuro, já o dissemos. Se nos concentrarmos nas frases (4) a (7) podemos admitir que o verbo ir veicula uma ideia de movimento prévio à acção propriamente dita. O sujeito desloca-se para ver um filme (note-se que se vir o filme em casa dirá «Ontem vi um filme»), desloca-se para falar com alguém; desloca-se para fazer ou concluir um trabalho.
O que é, do meu ponto de vista, estranho na frase (3) é esta repetição da mesma ideia, é o facto de alguém se deslocar, para se deslocar, que é, afinal, o que significa sair. Pessoalmente também concordo que há alguma coisa menos adequada na frase «Fui sair». E essa inadequação é semântica, ou seja, ocorre no âmbito do sentido veiculado pelo conjunto. Compreendo por que se usa: por analogia com o que acontece nos exemplos (4) a (7). Prefiro, de longe, «Ontem saí».