Webmock uses Addressable::URI and its === method for matching URIs. This has one flaw, which is that matching fails if two urls are identical sans the fact that their query values are in different order:
u1 = Addressable::URI.parse '/path?foo=bar&baz=kuuq'
u2 = Addressable::URI.parse '/path?baz=kuuq&foo=bar'
u1 === u2 #=> false
This means that if you've stubbed an http response using u1, an HTTP request to a path in form of u2 is not going to match this and is going to fail.
I've submitted this as bug 28 in Addressable but it's not going to get fixed.
I've monkeypatched Addressable for myself but I don't think this is a way to go. I think Webmock should have its own method for URI comparison: it can use Addressable::URI#=== to compare everything up to query string, but then it should compare query strings itself by ignoring query value order.
My monkeypatch: https://gist.github.com/832913
This issue has been fixed by sorting query values in WebMock::Util::URI.