Was this ever resolved? It's plaguing me as well.
Basically what I'm seeing happen is that a REQUEST_URI shows up as /%7Ewls/blog/, and while Apache it more than happy to deal with that, WordPress has some brain damage in recognizing that a URL with %7E in it is the same as one with a tilde in it.
Like you, any links using a tilde work:
And, like you, any links using the escape encoding do not:
Obviously Apache is delivering up a WordPress template, meaning it's found the directory. But it's the WordPress code that can't figure out the URL to pull up the correct entries.
I've tried poking around with mod_rewrite rules as well as WordPress's PHP code. At the moment I'm not having much luck, as I think the page determination code happens well before I get around to fixing the string to a familiar form.