How can I correctly include a (non-fragment) # in a URL?
You are correct ... it is invalid to use the "#" for anything other than a fragment. That does not mean that someone doesn't have their web servers setup in such a way that "#" can be used in the URL itself.  


  I'm guessing this is a problem with hash segment handling. Is there a right way to handle a URL like this?


To be clear, there is no problem with how Drupal is handling URLs ... Drupal is following the spec. I think your best bet in this case (short of yelling at whoever is giving you this URL for doing so) is to extend the Url class and replace the formUri method to handle your weird case. 

Your other option is to do something really hacky like putting an easily replaced string in the URL and then doing a string replace at the last minute before displaying it.