I would script it using Expect.pm or just plain old expect.  helo foo; mail From:  blah@feh.org; rcpt To:  me@me.org will give you an excellent idea if it's open or not.

* Mr Mine Sakiyama (msakiyam@yahoo.com) wrote:
> Hello.
> Is there a program that I can run on NetBSD that
> checks hosts for open relay? I have used rlytest,
> which seems too simple,, also tried mrt (mail relay
> tester), not getting much luck. Wondering if there are
> something else. 
> 
> Thanks
> 
> Mine
> 
> __________________________________________________
> Do You Yahoo!?
> Yahoo! - Official partner of 2002 FIFA World Cup
> http://fifaworldcup.yahoo.com