new domain - it goes straight into ppl's junkmail box!!

how do i solve this?? it's like a catch-22! i want to let people know i have a new email address, so i send an email from that domain, but their email client thinks it's spam because it doesn't recognize the domain.. the only thing i can think of is to send TWO emails, one from, like, gmail, and one from the new domain. the gmail one says "if you don't have another email from me, please check your junkmail, find it and mark it as not spam"

hardly slick, though