We're with our bank for about 5 years, never been in the red, with perfect accounts and fully tax compliant. Despite all this, we're finding it pretty difficult to get an overdraft from our bank. They want loads more info.
I don't think length of time with the bank is the main determining factor.
My wife can easily get €12k on her credit card though, no questions asked.