You're saying that whether or not it's advertising depends on the context of where the paid ad appears, which is an arbitrary and baseless distinction.
If a company rents a billboard that's right outside their office, isn't that advertising? Sure, you could have looked at the front of the building to see their logo, but that doesn't change the fact that the billboard is advertising.
I disagree with your analogy. In your case, I would say the banner represents the giant logo over the door, just before you walk into the building.
In most ad-based marketing, you're typically not just randomly throwing your brand out there. Obviously, the expected ROI goes up when you can target the right demographic (saturday morning cartoons versus world news with Tom Brokaw). This is not that. This isn't a demographic-driven ad, based on search criteria like "airline travel" or "buy tickets from DEN to DTW". The person knew exactly what they were searching for. Hell, depending on your browser, typing that exact string in your address bar will take you directly to Southwest Airlines. Google just managed to convince companies to pay them for this, while at the same time presenting a prettier and more useful direct links within that box.
As an afterthought, the most-searched for term in our company web portal is "google". I would be extremely surprised if Google, themselves, don't have a ton of searches where they could simply append a ".com" to the search query and send them directly to where they wanted. I doubt my parents would even notice.
If a company rents a billboard that's right outside their office, isn't that advertising? Sure, you could have looked at the front of the building to see their logo, but that doesn't change the fact that the billboard is advertising.