You need to confirm that the DNS TXT records for DKIM message signing are being served and match the selector used in the DKIM header

DKIM signed email contain a DKIM-Signature header that contains a reference to which DNS TXT record is to be used to get the DKIM public key.

DKIM-Signature: v=1; a=rsa-sha256; d=example.com; s=dkim1; c=Relaxed/Simple;
        q=dns/txt; [email protected]; t=1270733902; x=1273325902;
        h=From:Sender:Reply-To:Subject:Date:Message-ID:To:Cc:MIME-Version:Content-Type:
        Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date:Resent-From:
        Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Id:
        List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive;
        bh=B660J73Ft0QbE3LMW3JCAtDfTx92PLNLsV88VF8S2u0=;
        b=Xr0BKE5GaOfNzpXzRA4KNEk+Vy51hs9yprAjbHGKg858pUWSWK4uHRKsT459yfBj
        eus3lyfpVzzvD15Oyy0iWqe6HvJm/Ad34O1s6UsTnCB3v5CnUkQUCVLsrsoVm8SK
        j+ULj1MxMfZFgVG6UbjE3FMs/WgJx15AhUrgglSi/Gg=;

The contents of the 'd=' and 's=' parts of the DKIM signature give you the domain and the selector used to generate the signature. To look up the key used to generate the signature you need to look up the TXT record for the following host name: [selector]._domainkey.[domain] where the 's=' value is the selector and the 'd=' value is the domain.

In the example header above the correct nslookup would be as follows:
 

vm-sbg> nslookup -type=txt dkim1._domainkey.example.com
Server:         127.0.0.1
Address:        127.0.0.1#53

Non-authoritative answer:
dkim1._domainkey.example.com       text = "v=DKIM1\; k=rsa\; h=sha256\; p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCVVtgHlIqIHiakZWIT+0e7beht/
iKH0FUsryhWOop2VbLye2BRwZfEhAiZEHossXdLjKLW7TgO8InesczrVxHtXHgfPlXM4Myn7yPPXm2E9xq8XiLtS7
mymvv73FF3ixOv+RSca45mQM+DUyCI37CHBBaqCEcSvr8Y70i3OMDIhQIDAQAB"

Authoritative answers can be found from:
example.com     nameserver = localhost.
localhost       internet address = 127.0.0.1
localhost       has AAAA address ::1

Currently the Administration > Utilities > nslookup page will not accept a valid DKIM hostname for a TXT record search. You will need to use to CLI nslookup command as shown above.