I use the <address> tag, but that's technically not what it's for. Luckily, no user agent gives a rat's : )
<address> was intended to display information, such as a name, url, and/or email address, of the person who posted/wrote the information. Since this was designed back in the heady days of BulletinBoards, think plain text mailing-list imitation where one university sends a document to another university.
So I figure, meh: if it's the postal address of the one who owns the site (and therefore created the content), why not.
I use it like so
first line <br>
second line <br>
If you're listing multiple postal addresses (more than 2), each address likely belongs in a li within a ul.
Whether you use a br or CSS to make newlines depends on whether the newlines are considered part of the address, which might mean the format the user needs.
If I'm writing an address that explains to a user how to send us a mail, I use the br's, because this is what the post office expects, and so the multi-line format is necessary information... especially when it's an address that is foreign to the visitors.
3.) Should I use a <li> for each line, and an <ul> for the Address as a whole?
No. Each line can't stand alone as its own item. It means nothing without the other parts of the address, whereas a list such as a list of links (like a menu), each link can work and be viewed fine on its own.
4.) Possibly a <dt> and <dd>?
If you supplied dt's, though for most visitors those would be redundant:
<dt>Company name: </dt>
<dt>Street Address: </dt>
<dd>123 Foo Lane</dd>
<dt>Postcode, City: </dt>
The address needs to larger font since it is on a "Contact Us" page, and really the only thing on the page. (Maybe it could even be an <h2>?!)
If it's not heading other content, I wouldn't make it a header, no matter how important it is. The h1 (or whatever you're using as main page header) would say "contact" or "contact information" so the address underneath is plain content being headed... just make it bigger with CSS.