Would it be possible to make a coin that could only be mined if you had SSE instruction set 1,2,3, etc? As far as I know no GPU would be able to decode something that required one of those instruction sets.
This doesn't make sense: the code has to be open source and therefore any competent programmer could rewrite it from SSE/AVX/etc. to the vector instructions of the GPUs. And the GPUs are much faster at single- and double-precision floating point (32-bit and 64-bit).
The thing that handicaps GPU is the extended-precision (80-bit) floating point. It isn't impossible to emulate it on the GPU, its just that the results will be significantly slower and will require significant development effort that will be of little use anywhere else.
There are various quad-float (128-bit) libraries is where the multiple-precision floating point development work is geared.