In my experience, there are several factors here:
1. Acting "in character" during combat usually involves a certain degree of suboptimal decisionmaking. If everyone is playing a trained tactician who fights dirty taking every possible advantage, then, to some degree, you wouldn't be able to tell if they were role-playing. On the other hand, if you have a Sturm Brightblade type paladin who refuses to flank intelligent humanoid opponents (striking from behind is dishonorable) and who won't strike foes who are blinded, stunneed, or prone, then combats that would otherwise be easy might be difficult and those that would otherwise be difficult become deadly. If the deadliness factor is cranked too far up, players may well feel that there isn't room to role-play such a character. (Also note that mini-less combat won't help this kind of role-playing in the slightest).
2. Out of character chatter is probably one of the biggest contributors to not role-playing in combat. If every character's move is a group decision ("You should attack him; I need help/If you move here, you can avoid AoOs/No, don't avoid AoOs, provoke them and draw the AoO so I can withdraw") then you'll find the role-playing reduced in two ways. First, since everyone is discussing each character's move, they're likely to arrive at one of the better moves but it's unlikely to seem like role-playing. Secondly, it removes the role-playing potential that is in-character communication.
What I would suggest as a way to start introducing more role-playing into combat is to:
1. Slightly dial down the intensity of combats so that non-optimific moves aren't terminal.
2. Prohibit group decision-making. "It's his character; he knows the rules; let him decide what to do."
3. Have your NPCs demonstrate by talking to each other. If the NPCs effortlessly move to flank and always know what the other one is planning, it's not surprising that the PCs do so too. If, on the other hand, the NPC warrior yells, "help! I need some healing!" and the rogue yells "double team him" when he delays or readies an action to attack the PC as soon as he gets a flank, players may get into the same act.
4. Sometimes have NPC plans fail because they don't act as a team. The NPC rogue moves and readies an action to attack when he gets a flank but the NPC fighter steps back and drinks a potion instead of flanking. Etc. Just because a move would be optimific for Team Bad Guy (TM) doesn't mean that it's a good idea for any particular NPC. Evil NPCs (except perhaps for the Krazy Kultists of Doom) generally don't like to be sacrificed for the greater good of their masters or even their companions. Since it's all about them, there's no point to it.