Dei uma pesquisada porca no Google e dizem que veio do inglês mesmo, assim como "oxente" (
Oh, shit!), "forró" (
for all), "ei!" (
hey), "uau!" (
wow). Parece plausível.

EDIT:
"Acredita-se que a origem do «uai» estaria na fusão das interjeições opa! (ou upa!)+ôi+ai, que aparecem assim juntinhas, por exemplo, na página 353 de Sagarana, o grande (em todos os sentidos) romance do escritor mineiro João Guimarães Rosa.
A essa hipótese podemos juntar uma outra. A que Luciano de Oliveira Fernandes, um professor mineiro, defendeu no V Congresso de Ciências Humanas, Letras e Artes, realizado na Universidade Federal de Ouro Preto, em agosto de 2001.
Segundo ele, tudo começou quando um vilarejo chamado Gongo Soco, onde se explorava ouro, foi comprado pela “Imperial Brazilian Mining Association”, o que resultou na instalação da primeira empresa britânica em Minas Gerais. Durante as quase três décadas, de 1824 a 1856, que os ingleses ali estiveram, Gongo Seco, afirma o professor, foi transformado numa autêntica vila inglesa. E passo a citá-lo:
«Pode ser atribuída ao convívio com esses e outros ingleses que residiram na província a utilização por parte dos mineiros da interjeição "Uai!" (que exprime surpresa e/ou espanto), a qual possui semelhanças fonéticas e semânticas com o vocábulo "Why" utilizado na língua inglesa com o mesmo sentido do nosso "por quê?", ou como interjeição, assumindo, neste caso, o mesmo sentido do Uai mineiro. Notemos que o Uai mineiro e o "Why" britânico possuem a mesma representação fonética; e notemos ainda que o Uai é a expressão da língua portuguesa falada no Brasil que mais se relaciona com a identidade mineira.»
Os ingleses foram embora, mas o Uai nacionalizou-se. Ou melhor, mineirizou-se. Segundo o prescrito nas Noções de Mineirês para ‘estrangeiros’, «Uai é indispensável, significa nada e tudo ao mesmo tempo. Tudo depende do contexto e da entonação."
http://ciberduvidas.sapo.pt/php/resposta.php?id=12679___
Como se pronuncia
voucher?