Solution deployed in Central Administration, but Web Part missing

I have WebApp at URL http://AUrl/

I have deployed solution with single file in _layout. And then removed that solution and installed upgrade with new web part in it.

I can see in Central administration that my solution is deployed to http://AUrl/

I can not see that web part on http://AUrl/site/SomeSiteHere.

Any ideas?

PS I do not have any actual content under http://AUrl/ accessible via web browser.

Edit: Above feature was scoped as Web App. I have tried a bit different approach where feature is scoped as Site. Still no luck! Central admin see it, http://AUrl/site/SomeSiteHere do not.

Update: When I have set site url, for second solution (scoped at site!), VS was able to deploy it successfully.

So the question now is:

How do You deploy solution to web app, when there is no site collection set for web app url? Like http://AUrl/ is web app url only, and site collection is set at http://AUrl/sites/SiteA.