The NonBlocking example in the latest version of the Sensirion library has some example error checking code that may be of use. I'd be interested to see how it behaves in your case.
Also, 3.3V for the pullups? (Data should be the only signal that needs one). I assume that means you are using 3.3V to the sensor. I know there is a note in the data sheet saying to use a 3.3V supply voltage "for highest accuracy" but unless your Arduino is also running on 3.3V, I think you are just reducing noise margin on the interface for no real gain. The library temperature coefficient "D1" assumes 5V so you do need to change that if you use a different supply voltage. Otherwise, you'll be off by 0.4-0.5 degrees C.
Thanks for the new library version. I will give that a go; possibly even tonight.
The 3.3V is a historic thing. The Melexis sensor does only work on 3.3V and is not 5V tolerant. So I disabled the internal pull-ups on A4 and A5 (the I2C bus) first thing in my sketch and pulled up SDA and SCL to 3.3V externally. This seems to work fine.
When I connected the SHT15 parallel to the Melexis I thought it should work fine on 3.3V too. Haven't actually given that much thought as 3.3V seems to be a valid supply and logic level for the SHT. And the SHT has worked when connected parallel to the Melexis, just never in the same sketch.
But since the SHT now has its own lines, I can easily wire it up to 5V, just to rule this out. BTW, for now I'd be happy to be .5 degrees off as long as I got any results... 
I've seen in the SHT data sheet that only the data line has a pull-up. Would it actually be wrong to pull up the clock as well? The breakout board my SHT came on did have a 1k pull-up on both lines. I've removed these though before connecting it to the I2C bus as that was already pulled up. Now with the SHT on its own lines I can choose which one to pull up and which one not.
I was also wondering whether it would be worth trying that interface reset described in the data sheet if I still can't communicate with the SHT. But they aren't really saying what exactly that reset does. Is that the same as your Sensirion::softReset() function?