port 587 is what I use for smtp. It is a standard alternative I think
I wonder if k9 simply isn't up to the task. I have old imap software on my mail server so there isn't a droid client that handles it.
This might be a stupid question, but is this an exchange server?