Some keypads are a mechanical contact creating a short when a button is pressed, there will be less than 1 ohm between the row and column selected, conductive rubber keypads can be a few tens or a 100 ohms or so, meaning the pullup resistor needs to be higher, more like 1k to 10k, depending on the actual resistance of the uP input port , a pic16f628 has worked well for me with 4k7 pullups.
I've never used the tristate technique, though it sounds more energy efficient, my code puts a logic 0 on all the rows and waits for a 0 on one of the colums, ie a button pressed, then a 0 is shifted along the rows untill the actual key pressed is found.
I'm sure theres better ways of doing it, thers some clever ways that only use a few pins, one method uses just 1 pin.