Is it possible to debounce the encoder just like a pushbutton switch? if ever?
Possible, contact debouncing is either done with hardware using external resistor/caps or in software using delays. but I can't tell you specidic hardware values of caps and resistors or how to wire it up. And software delay() doesn't work inside of ISR routines because all interrupts are disabled at that time.
Not sure what further help I can give you. I first played around with a cheap mechanical encoder switch a couple of years ago and never was happy with it's performance. I finally found a cheap optical encoder at a surplus dealer and that worked great.
Dealing with contact bounce and using interrupt inputs is a difficult task at best.