We need to receive data via URL from one of our clients.  We have a
PHP script to collect the variables in the string, however, it looks
like they may be sending over bad characters, including the pound sign
(#).  Of course, all data in the string after the pound sign is lost. 
Is there a way to clean the string before extracting the variables? 
I?ve tried removing the pound sign with preg_replace and str_replace
on the query as $_SERVER['QUERY_STRING'], but no luck.

URL example:

http://oursite.com/script.php?name=John&address=303%20Main%20St%20#101&city=Pleasantville&state=TN
. . .

The only thing i can come up with out of the box, is if you are able
to change the URL Query sent to you from your client? and if so
replace # with %23 in the query sent to you.

This would give you these $_GET variables:

name : John
address : 303 Main St #101
city : Pleasantville
state : TN

Instead of the earlier:

name : John
address : 303 Main St 

"I?ve tried removing the pound sign with preg_replace and str_replace
on the query as $_SERVER['QUERY_STRING'], but no luck."

well 
$_SERVER["QUERY_STRING"] =
name=John&address=303%20Main%20St%20
in the particular case so the query is cut off after the "#"

Btw an easy way to see what $_GET and $_POST variables are set is to
run this little snippet:
<?php
 foreach ($_GET as $a => $b)
 {
 	echo $a . " => " . $b . "<br/>";
 }
?>

and changing to $_POST to have a look at those variables.
Hope this helps you.