DNS: Is it valid to have an "MX" record and no "A" record?

As long as the system pointed at by the MX record has an A record itself, then yes.

For example: example.com can have a MX record pointing at mail.otherdomain.com. As long as the name mail.otherdomain.com itself is resolvable to an IP address, this is a valid configuration for example.com.

Strictly speaking, mail.otherdomain.com should be an A record with the IP address in order to be RFC-compliant. But this A record will be in the otherdomain.com domain, not in example.com.

Addressing your example, in order for [email protected] to be a valid email address, mail.otherdomain.com needs to be configured to handle inbound mail for [email protected].