<!--adicionei um `align='right'` na <table> você também pode tentar colocar um `style=margin-left=auto` -->
<table align='right' border='1' cellspacing='0' cellpadding='0' style='border-collapse:collapse;border:none;mso-border-alt:solid windowtext .5pt;mso-padding-alt:0cm 3.5pt 0cm 3.5pt;'>
<tr style='height:58.75pt; mso-yfti-lastrow:yes; page-break-inside:avoid;'>
<td width='617' valign='top' style='width:462.5pt; border:solid windowtext .5pt;padding:0cm 3.5pt 0cm 3.5pt; height:58.75pt'>
<h1 align='left' style='text-align:left'> </h1>
<h1><span style='font-size:12.0pt'><#NOME_PREFEITURA><o:p></o:p></span></h1>
<p class='MsoNormal' align='center' style='text-align:center'><b style='mso-bidi-font-weight:normal'><#DEPARTAMENTO_PREFEITURA><o:p></o:p></b></p>
</td>
</tr>
</table>