It looks like Maxim will allow free samples of the part you suggested 
I'm not really surprised the Due failed to give a good result, you're probably just reading noise, a reading of 5 equates to 4mV, which is higher than you got with the meter, I wouldn't expect that to be the case unless it was noise.
What were the figures you got using the Tp(V) maths?
I'd probably go for the Maxim part at this point, it looks like you can set the device to 'custom' and read the raw data out which you can then convert to temperature.