After any exchange between the app and Google play to purchase some goods,
the app must then forward this request to some external content-delivery
server requesting that the purchased goods be delivered.

Obviously, there is no way to prevent the user from modifying the source
code of their app from simply sending any arbitrary message -- such as a
"purchase was successful" message to your server (obfuscation may slow down
attackers, but isn't truly secure).

Therefore, the only way to be secure is if the "purchase successful"
message has been digitally signed by Google play.  The only mention of this
I found in the documentation is here:
http://developer.android.com/guide/google/play/billing/billing_integr...

where it says:  "*Your application must also provide a way to verify the
signatures that accompany every PURCHASE_STATE_CHANGED broadcast intent.
The Security.java file in the sample application shows you how to do this.*"

Now, if we look at the source code for Security.java (inside the Dungeons
example they are referring to), then we find the "verifyPurchase" function,
which contains this code:

/**
             * Compute your public key (that you got from the Android
Market publisher site).
             *
             * Instead of just storing the entire literal string here
embedded in the
             * program,  construct the key at runtime from pieces or
             * use bit manipulation (for example, XOR with some other
string) to hide
             * the actual key.  The key itself is not secret information,
but we don't
             * want to make it easy for an adversary to replace the public
key with one
             * of their own and then fake messages from the server.
             *
             * Generally, encryption keys / passwords should only be kept
in memory
             * long enough to perform the operation they need to perform.
             */
            String base64EncodedPublicKey =
"MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAqiPOV7jXSWomX32h9KYRfWXOLEbmak AQJhq5lq1j1tEC3Tz8qvO9RUAmaCKF1x51Wyc5zI4weX5N1Wix/RdpvAFPk4O5PmGcCpA78grFM PFLZtwI9R1cOtlOSwoRBMc2PDdGVWsLWyWoNhsnkOXMvfOk78daT0reFFFdMPmACzROcwcW/Dq+ gkE4sTb2fgtLlYLOAy186PTHuES+j+532jbuOBFLLVw64UYjTcP29LdIVC/XBvqqiMdMLeDblvQ yQVhoQcFvOwf0+k0ZJUdNcZcJXgQJC0fsMOaWu/aTzqm5fqQcboYDko/lG76+lNqS71wkWefKAz zkGHjyrZS6AwIDAQAB";
            PublicKey key =
Security.generatePublicKey(base64EncodedPublicKey);
            verified = Security.verify(key, signedData, signature);
            if (!verified) {
                Log.w(TAG, "signature does not match data.");
                return null;
            }

Now, this seems odd to me...because they are using OUR OWN public key to
verify the signature.  The Security.Verify would verify that the supplied
public key had been signed with the corresponding PRIVATE key.  But Google
Play does not have access to our private key...so how could they have
signed it for us?  

Secondly, it does not make sense to do verification on the client side.  
The verification needs to be done by the content-delivery server, to verify
that the message came from Google Play -- which means that Google should
have signed it with THEIR private key.

Please help me understand how this makes any sense!

This licensing / billing key pair is a different one. As you already
stated: it cannot be your company's private key because Google is not in
possession of it. When you register your Android Developer account Google
generates a private key which is only known to Google and that public key
which you can copy from your Android Developer Console.

Each billing transaction / licensing verification is signed by Google using
that private key. You can safely use the public key counterpart to verify
the billing transaction on your server.