Using an AES-256-GCM key as a salt to SHA-256 Assume 256 bit keys are randomly generated and data is encrypted using AES-GCM-256 prior to being sent to a server.

The goal is to enable the server to determine uniqueness of data it receives without actually revealing the plaintext data.

Would it be safe to use SHA-256 where the input to the hash function is the key in addition to the plaintext data -- so SHA-256(key + plaintext)? By safe I mean does doing this reduce the safety properties of the key by a significant margin?

If not safe, how large of a random byte string is needed to make the SHA sufficiently difficult to brute force?
I'd split the key into two 256 bit keys using HKDF, and use one key for the GCM mode, and the other for the hash over the plaintext. However, I then would use HMAC rather than SHA-256 as it accepts and the key as a separate entity in the application.

The advantages of the HKDF key derivation function is that there is more "distance" between the keys used for the authenticated encryption and hash function. That said, just reusing the key is not likely to introduce direct vulnerabilities. It's also more "neat" using a KDF to derive other keys for other purposes, from a single shared secret key.

The advantage of using HMAC is that you are protected against length extension attacks. Furthermore, HMAC explicitly accepts a key rather than just data, so the key may be better protected against attacks, depending on the system that it is used on of course.

Otherwise, yes, using a hash over the shared secret and data may be used to determine uniqueness (well, with a high degree of certainty in the case of cryptographic hashes, of course), assuming that the key doesn't change during the time that this property is required. So yeah, I don't see how this would not work (but please don't view that as scientific proof).