reverse the order so that your replacing the spaces with underscores directly on the recordset result, then using the preg_replace to strip other characters:
<?php echo(preg_replace("/[^A-Za-z0-9_]/", "", str_replace(array(" "),"_", ($row_NewsRS['NewsTitle'])))); ?>