By seeking feedback you're asking users to do something for you - to do you a favour.
Providing a service and saying 'once you're done, let us know what you think.' just does not work. Once people are done with the service, they rarely go back and find the feedback form. I've seen this happen where no-one gave feedback because the request for feedback came via the original email with a link to the website beta.
So how do you get people to give feedback? You have to appeal to the subconscious element of the user to make them want to give feedback. In order to do that you are targeting the goodwill of the user. This means that you want to make the user feel as though you have done them a favour first and that they have a duty to respond by doing you a favour back.
Often this reciprocal behaviour is magnified and users will respond by doing much more of a favour than you gave them in the first place.
So where I'm going with this is that when asking for feedback, it's not about location, it's about timing. By placing a feedback banner on the page from the beginning, you may actually be diminishing the likelihood of getting a response because it's being displayed before it's required, and the impulse reaction is lost, with users getting used to it being there and feeling that it's irrelevant when they first visit because they haven't any feedback to give yet.
At some point in your service, you will hopefully have provided the user with a service and at a critical point the user should have a sense of completion or achievement and be feeling positive about the service. Yes - I know you're looking to collect negative feedback from the journey - but nevertheless, the journey must end, and that's the most likely peak of positivity and accomplishment.
At this point - when you have built up this goodwill or indebtedness, that's the time to appeal to them and get the impulse reciprocity reaction that makes them provide feedback.
So think about how you can tie in your feedback to this sequence of events, and position your request or alert in such a way as to provoke a reaction in this natural pause - where the user is not being interrupted, and has a fairly full pot of goodwill. By the way - if there are glaring issues that mean that pot of goodwill might never be filled, you should rectify them before putting out a beta and asking for feedback. Don't release what you know to be annoying because feedback on that will eclipse all the other things you really wanted feedback on.
In addition you might want to consider combining the reciprocity with reward and inform the user that they can receive a discount on the service when it goes live, or receive an exclusive invite at time of release - or something suitable, and relevant, and attractive depending on your service and your target audience. But you must do this at the same time as requesting the feedback. In tests, reciprocity beats reward by two to one. Don't offer the reward beforehand, wait until the reciprocal moment - then compound it with the reward offer.
Tip: Don't go all out and use up all your potential beta userbase in one go. Plan ahead to do it in stages, iterate quickly on initial feedback that will allow you to hone in on the most commonly referred issues, fix/improve them and repeat, preferably with a different userbase.
For more details:
tl;dr - Left, Right, Bottom - there is no single right answer - to elicit a response, you need to appeal to a much deeper subconscious emotion in the brain than just a left/right preference.