The search algorithm in the client and the Web API are indeed slightly different, but you may also have found a bug.
The Web API uses a global popularity to rank search results (weighted with the actual search query). It also returns things that is available in any country.
The client only returns entities available in the country for the logged in user. It also uses the popularity from the logged in user's country to rank search results.
Depending on this and also the fact that labels very often send different copies of the exact same albums for different countries with different rights will make the search result different. We recently saw a bug because of this in some countries in the clients as well. https://twitter.com/swemoph/status/426260017847623680
So, by design it should be slightly different, however in your case it should only mean more search results in a slightly different order, but never zero.
2-4 could probably be explained with not escaping &.
Number 1 is more interesting. Looking at the actual uri of the track in the Web API and also the open site, we see it is misattributed to Teddybears (not Teddybears Sthlm):
$ curl -s 'http://ws.spotify.com/lookup/1/.json?uri=spotify:track:1JdC88rtMAwebQVFOcAg0D' | jq .track.artists [ { "name": "Teddybears", "href": "spotify:artist:3gqv1kgivAc92KnUm4elKv" }, { "name": "Thomas Rusiak", "href": "spotify:artist:7amcWVAeY8e6YwgV9bXlKH" } ]
http://open.spotify.com/track/1JdC88rtMAwebQVFOcAg0D shows Rock 'n' Roll Highschool by Teddybears
This clearly explains why you don't find it in the Web API. By adding the search term sthlm you are excluding this track from the results. The query engine seems to work as intended (although I would have preferred if we allowed a more fuzzy search here, but that is a different problem). You are doing nothing wrong, but we need to figure out why the data looks different.