Can convolution of one signal with different signals give the same answer?
Convolution is filtering.  

Consider creating a filter with a rectangular response in the frequency domain.  Then any signal with the same content within the filter's passband, no matter what the signal content outside the passband of the filter, should result in only the content within the passband after convolution with the impulse response of the filter.  Thus, multiple inputs (signals with different stuff outside of the passband) to a convolution with this filter should result in the same output.

(Your opening statement merely swaps the frequency and time domains for the rectangular function, making this relationship harder to recognize.)

This should work even for a non-rectangular and finite length FIR filter with at least one zero in it's transform (maybe at a nice integer submultiple of the sample rate).  Add any magnitude of sinusoidal input at the frequency of the zero, and the convolution result or filter output remains unchanged (except perhaps for numerical issues/clipping/quantization/etc.).