gsz,
I think the answer to "is there any way to strip executable attachments out with Exchange without using 3rd-party tools" is no, you can't. I've tried, too. But, as folks here have noted, most Exchange-based anti-virus products can do it, and additionally several firewalls (Watchguard's Firebox for sure, not positive about others) will do the job as well before the email even gets to Exchange.
-Steve