Erro no Java Mail

Eu sempre uso o Java Mail da Sun quando preciso enviar um e-mail com um programa Java. Mas ultimamente ele tem dado um erro estranho. Quando tento enviar um e-mail para algum usuario do mesmo servidor ao qual estou conectado ele funciona perfeitamente mas quando me conecto ao servidor mas tento mandar um e-mail para qualquer outro canto ele informa que o endereço é inválido. O mais estranho é que dois clientes usavam aplicações minhas e elas funcionavam perfeitamente mas ao mesmo tempo que meus testes pararam de funcionar uma delas também parou de funcionar também.

Algo com o seu proxy ou autenticação smtp?