I think the issue is the line-height you are setting. I found that when the line-height is equal to the td height, valign=middle will not work properly in outlook.
The following will not middle-align the text:
<table cellspacing="0" cellpadding="0" width="100%" border="0" align="right">
<tr>
<td align="center" valign="middle" bgcolor="#b2112a" height="48" style="font-size:20px; line-height:48px;">
Link Text Here
</td>
</tr>
</table>
THIS WILL:
<table cellspacing="0" cellpadding="0" width="100%" border="0" align="right">
<tr>
<td align="center" valign="middle" bgcolor="#b2112a" height="48" style="font-size:20px; line-height:24px;">
Link Text Here
</td>
</tr>
</table>