Hmm.. there maybe some exceptions. I just tried using my
AXIS Bank Titanium Debit Card to purchase 'Beautiful Widgets' from Android market. And it worked flawlessly.
Didn't took more than 10 seconds for Google checkout process to finish and start the download.
Amount debited was 52.77/- for Google.com
(One time, I think)
And 5.27/- for App purchase.
It's a Mastercard and I have recently enabled Secure 3D login for it but it didn't ask for that.
Here is a screenshot of my e-mail receipt. I know it doesn't indicate anywhere that I used a debit card, so you will have to take my words for it.
*i44.tinypic.com/34xqjow.jpg