Should <br /> and <hr /> be avoided at all costs in web design?

<hr /> and <br />, much like everything else, can be abused to do design when they shouldn't be. <hr /> is meant to be used to visually divide sections of text, but in a localized sense. <br /> is meant to do the same thing, but without the horizontal line.

It would be a design flaw to use <hr /> across a site as a design, but in this post, for instance, it would be correct to use both <br /> and <hr />, since this section of text would still have to be a section of text, even if the site layout changed.

<hr/> and <br/> are presentational elements that have no semantic value to the document, so from a purist perspective yes, they ought to be avoided.

Think about HTML not as a presentational tool but rather as a document that needs to be self-describing. <hr/> and <br/> add no semantic value - rather they represent a very specific presentation in the browser.

That all being said, be pragmatic in your approach. Try to avoid them at all cost but if you find yourself coding up the walls and across the ceiling to avoid them then its better to just go ahead and use them. Semantics are important but fringe cases like this are not where they matter the most.

Just so long as you don't use <br/> to form paragraphs, you're probably alright in my book ;) I hate seeing:

<p>
  ...lengthy first paragraph...
  <br/>
  <br/>
  ...lengthy second paragraph...
  <br/>
  <br/>
  ...lengthy third paragraph...
</p>

As for an address, I would do it like this:

<address class="address">
  <span class="street">1100 N. Wullabee Lane</span><br/>
  <span class="city">Pensacola</span>, <span class="state">Florida</span> 
  <span class="zip">32503</span>
</address>

But that's likely because I love jQuery and would like access to any of those parts at any given moment :)

There is nothing wrong with using <br /> or <hr />. Neither of them are deprecated tags, even in the new HTML 5 draft spec (relevant spec info). In fact, it's hard to state correct usage of the <br /> tag better than the W3C itself:

The following example is correct usage of the br element:

<p>P. Sherman<br>
42 Wallaby Way<br>
Sydney</p>

br elements must not be used for separating thematic groups in a paragraph.

The following examples are non-conforming, as they abuse the br element:

<p><a ...>34 comments.</a><br>
<a ...>Add a comment.<a></p>

<p>Name: <input name="name"><br>
Address: <input name="address"></p>

Here are alternatives to the above, which are correct:

<p><a ...>34 comments.</a></p>
<p><a ...>Add a comment.<a></p>

<p>Name: <input name="name"></p>
<p>Address: <input name="address"></p>

<hr /> can very well be part of the content as well, and not just a display element. Use good judgement when it comes to what is content and what is not, and you'll know when to use these elements. They're both valid, useful elements in the current W3C specs. But with great power comes great responsibility, so use them correctly.

Edit 1:

Another thought I had after I first hit "post" - there's been a lot of anti-<table> sentiment among web developers in recent years, and with good reason. People were abusing the <table> tag, using it for site layout and formatting. That's not what it's for, so you shouldn't use it that way. But does that mean you should never use the <table> tag? What if you actually have an honest-to-goodness table in your code, for example, if you were writing a science article and you wanted to include the periodic table of the elements? In that case, the use of <table> is totally justified, it becomes semantic markup instead of formatting. It's the same situation with <br />. When it's part of your content (ie, text that should break at those points in order to be correct English), use it! When you're just doing it for formatting reasons, it's best to try another way.