It should give you a new address every time. However, IIRC, there's sometimes it won't if the keypool has not been refilled recently. For the keypool to not be refilled recently, you would have had to have requested the number of addresses in your keypool since the last time your wallet was unlocked.
Could you post the debug.log?
That is exactly what I thought. But that is impossible, I have 10000 addresses in this wallet & rarely use it. What kind of debug were you referring to? From the debug.log file?