> Can you send mail from something that doesn't have a DNS entry?

You never really could. Participating in public email exchange requires that the sender can resolve then "fully qualified" domain in your return address. Except after prior agreement or authentication, messages simply that fail this are not generally accepted.

> If your headers are correct, are you guaranteed mail bounces for un-deliverable emails?

Even better: You are more likely to see an immediate refusal instead of a delayed bounce, if the recipient exchange can during transmission already determine that they do not want message claiming to be originally transmitted from X to Y yet breaking their ability to check the signature added by X.