Ah-ha. The kbs=\b tells us that vi will be expecting a normal ^H to be sent by the Backspace key in Putty. Your putty must be sending ^? instead (since that's what stty -a said and you didn't complain about the Backspace not working at the command line). This means you have two choices.
You can use stty erase '^h' so that the system thinks the right character is ^H and tell Putty to send the same (I don't use Putty, but I think it's under Settings > Terminal). Or, you can create a terminal configuration for vi that overrides the one in that default configuration (I'd have to look that up as I don't remember the details for that on Sun's vi command).