Hi Jon,
I was looking through our old support tickets and found a similar issue to the one your described. In that ticket, the culprit ended up being the Output filter settings for the site. (Admin / Settings / System / Output filter). In the tickets I found, the answer was to reset those settings to the default. Is it possible you have some settings set in this area of your site that are affecting how the site is functioning?
I also found an older article (v6/7) that discussing how to handle when ~'s don't resolve correctly, which may also be of help.
http://devnet.kentico.com/articles/issue-with-tilde-character-(~)-not-being-resolved-correctly-in-links