You cannot put query string parameters in the original URI path of the Redirect directive. To do this, you need the mod_rewrite %{QUERY_STRING} :
RewriteEngine On RewriteCond %{QUERY_STRING} ^id=123$ RewriteRule ^/?product\.php$ http://website.com.au/product_123.php? [L,R=301]
Or make it more general:
RewriteEngine On RewriteCond %{QUERY_STRING} ^id=([^&]+) RewriteRule ^/?product\.php$ http://website.com.au/product_%1.php? [L,R=301]
source share