Is it really a cipher ? It look like a base64 encoding or something like that.
The best way to get information about the toolbar is to run a web server like apache on your windows pc, and put google.com as 127.0.0.1 in your host file. Then navigate freely on a lot of websites and collect all the url given by the toolbar right in your web server log files.
The last version of the toolbar introduced many enhancement and many new thinks are done a little bit differently (new seed for the hash, some change in the format of the url to get pagerank info,...).
So the fact that sometime you have query time and sometime not is only due to the version of the navclient...
If you find something interesting please share it with me by sticky.