Credit Card Call, Real or Scam? Time for 2-Factor Phone Authentication?

A couple of days ago, I received a call from a credit card company that I'm holding credit card with them. I was asked for my address to confirm my request of card replacement. Well, I didn't request for any card replacement! That raise a big alarm to me, so I was very reluctant to reveal anything with him. This is how it goes, paraphrased:

Me: I didn't request for any card replacement.
Him: From our record, it shows that you've request for a card replacement, on Nov 7.
Me: (after thinking..) Well, could it be a card upgrade? I did request for a card upgrade.
Him: I'm not sure if it is a card upgrade, as our system didn't show that information, it is a card replacement.
Him: Anyway, I need to confirm your address for the delivery of the card.
Me: Ok, can you tell me the address that you are going to send to?
Him: Before I proceed with that, I need to verify you are the Card Holder, may I have you NRIC No?
Me: Errr... mm... Why don't you just tell the address and I just confirm with you.
Him: Sorry, I have to verify that you are the valid card holder first before proceeding.
Me: (.... pause for awhile to think...) That sounds suspicious! I mean....
Him: (... also paused, he seems puzzled as well)
Me: I didn't ask for a card replacement after all!
Him: Okay, did you hold the credit card no. xyxy-xyxy-xyxy-xyxy?
Me: (After checking ...) No, I didn't have that card. I have 2 cards with you, but none of these 2 has that number.
Him: Okay, let me tell you what cards you are holding, you have one card zyzy-zyzy-zyzy-zyzy and another byby-byby-byby-byby.
Me: Oh yeah, you are right!
Him: Can I ask a few questions for verification purpose?
Me: Yes, please.
.... it continues as usual .. and I passed the verification.

Yesterday, I've received my "replacement" card, which essentially a card upgrade.

But looking at it, it is still possible for someone to imitate the call and I really can't verify since the caller ID doesn't mean anything nowadays (can be forged). I guess next time when I encounter this again, I'll get his name and extension and then make sure that I can call him back thru the bank's official number. Some sort of 2-Factor Phone Authentication? anyone?