No, DKIM and SPF don't disable mail relaying entirely. Instead, they only allow authorized relays to relay mail for a domain, and recommend that all receiving systems reject mail from unauthorized relays. This authorization is announced via special DNS records.
It is possible to setup several outbound relays (your own server and some external servers) at the same time. But you'll end up with listing them all in your SPF and DKIM records.
For SPF, you must either know all of relay IP addresses, or a name of their SPF valid record which lists all their addresses. You then set up into your SPF record all of those addresses, or use include:their-spf-record, in addition to your own or other relays you need:
example.com. TXT "v=spf1 a:your.server.name include:their-spf-record ip4:192.0.2.111 -all"
(there may be many different a:, include:, ip4: parts).
For DKIM, relay operator must generate signing key pairs. Then they must tell you the public key and its selector (they also configure their server to sign using corresponding private key and this selector). Then for each key-selector pair you create additional TXT record of the form:
selector._domainkey.example.com. TXT "v=DKIM1; k=rsa; p=..<key>.."
Of course, each system must use its own distinct selector.
This is all DNS setup needed to send mail with "from" domain from several systems simultaneously.
The SPF part shouldn't have any difficulty for anybody. The problem with their system might be they don't know how to set up DKIM signing for relayed mail. In my case, for example, postfix+rmilter does this and it has no problems, all can be configured. Also you can choose to sign with DKIM on your server which uses the relay as the smarthost, and you have to assure relay systems don't mess with signed headers and don't remove your signature; if so, there is no need to setup additional DKIM signing on relay system.
