It was noted in one of the trade publications I looked
at that a very
 effective check on SPAM was to confirm that the stream opened up to
 you (on your port 25) actually did a "conversation" with the remote
 player. 
I wouldn't call this "very effective".  It helps, but not all that
much - unless you combine it with banner delay or DATA delay, at which
point I think "very effective" does become accurate.
  Another [tack] might be to see if the sender HAS a
port 25 on their
 machine.  I suspect that the 'bot machines don't. 
Right - but neither do the outgoing mailhosts of large senders, large
enough to have divorced incoming functionality from outgoing
functionality.
  Unfortunately fixes like these require a deep diving
into the SMTP
 mailer at the code level. 
Yes and no.
If you want to implement them in your MTA proper, yes - though some of
the more modern MTAs already have such support present.  But you don't
*have* to do it there.
I wrote a "shim" program that accepts incoming SMTP connection and
passes them on to the real MTA when it gets a valid RCPT.  It was
designed to turn away bogus RCPTs very very cheaply (and it works
spectacularly well for that[%]), but it also does banner delay, DATA
delay, and early talker rejection.  (Because it connects through to a
real MTA in real time, it avoids the worst of the hairy issues that
plague MTAs, like queueing and retries.)
I wrote this for work, but they've given me approval to release it (I
asked preemptively); I can put it up for FTP if there's any interest.
[%] We once had a host from Korea or Taiwan or some such place open up
    some two hundred parallel connections and start a dumb-as-rocks
    dictionary attack.  We turned away some 10-20 thousand bogus RCPTs
    in about seven seconds - and never noticed; we had no idea it
    happened at all until I stumbled across it when reading logs for
    other reasons.  Even knowing exactly when it was, I couldn't find
    the blip in the load average data we collect.
/~\ The ASCII                           der Mouse
\ / Ribbon Campaign
 X  Against HTML               mouse at rodents.montreal.qc.ca
/ \ Email!           7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B