Question: Using element id's is the fastest way for javascript to 'get' an element. Is there a rule of thumb or best practices guideline on how many of these id's should be used before one can expect browser performance to start degrading?

Answer: 
An ID, in and of itself, is just an attribute value. The only 'performance' issue is extra bits and bytes the browser has to download. From a JavaScript POV, the more elements in the DOM, the longer it can take to traverse it, but that's not directly related to the number of IDs you may be using. 

EDIT:

To clarify if your JS is this:

```
document.getElementById("myID")

```

it doesn't matter if your HTML looks like this:

```
<div id="div1">
  <div id="div2">
    ...
      <div id="div999">
        <div id="myDiv">

```

or this:

```
<div>
  <div>
    ...
      <div>
        <div id="myDiv">

```

The JS should run the same for both of those examples.
A complex page means more bytes to download and it also means slower DOM access in JavaScript. It makes a difference if you loop through 500 or 5000 DOM elements on the page when you want to add an event handler for example.

A high number of DOM elements can be a symptom that there's something that should be improved with the markup of the page without necessarily removing content. Are you using nested tables for layout purposes? Are you throwing in more s only to fix layout issues? Maybe there's a better and more semantically correct way to do your markup.

A great help with layouts are the YUI CSS utilities: grids.css can help you with the overall layout, fonts.css and reset.css can help you strip away the browser's defaults formatting. This is a chance to start fresh and think about your markup, for example use s only when it makes sense semantically, and not because it renders a new line.

The number of DOM elements is easy to test, just type in Firebug's console:
document.getElementsByTagName('\*').length