I know that it generates new random address and new private key pair but I don't think I was ever able to get that private key on hands from that non-HD wallet service provider and they never let me sign messages through those newer addresses and that's what I was arguing here all about.
The issues you were having were not due to whether the wallet you were using was a deterministic or not... The issues you were having were because of your poor choice of wallet for your requirements.
Specifically, blockchain.info/com being somewhat feature poor and not providing users with the means to sign messages etc. Granted, it is a simple and easy to use wallet for users that simply want to be able to send/receive bitcoin and don't care too much about more "advanced" features like coin-control, signing messages, pay-to-many etc. I believe they
used to provide the ability to sign messages but that was removed... I'm not sure why? But then, this is the wallet provider that took months and months and months to implement custom fee settings, while users were forced to either pay ridiculously high fees... or have transactions "stuck" because of ridiculously low fees.
As you have now discovered, not all wallets are created equal, nor do they all provide the same features...