The property that the billboard is on is actually a different parcel than the one the building is being built on.
In regards to the billboard lease. 99% of billboard leases are iron clad and it's nearly impossible to negotiate out of them. Most leases have a clause in them that is the property is up for sale that the billboard company has first right to purchase the property at market value, this allows them to own the property if they so choose, this helps them to keep their billboard locations, because many new owners would not renew the lease.
Billboard leases are also range from 15-30 years.
Many people may say, the city should just use eminent domain on the billboards, but calculating the income of billboards over a 15-30 year period, and possibly beyond can be quite daunting. A billboard that size has a rate card price of $1954 per 4 week period (13 periods in a year) and there are 3 boards on that site. Billboard rates have an average increase of 8% per year. Not knowing the lease details on the property and not even including yearly rate increases, the estimated value on 15 more years of a lease, on three boards at the 2012 rate card value would be $1,143,090.