Fun fact: my address gets corrected to one on the other side of town with a South suffix added. The Post Office, UPS and FedEx all have manual procedures in place to handle this case. No-one has yet to fix their software more than to flag a manual review at the local office
Have you thought about requesting to change the number of your house to one that doesn't exist on the other side of town? That is usually much easier and cheaper than changing the street name.
