user4361: I bought an ATMega328P-PU and burned OptiBoot onto it using a second Arduino Uno R3 with great success.
I then put the microcontroller back on the (empty) Uno R3 (DIP) Board for programming, connected USB and uploaded the blink sketch successfully.
Now to the weird stuff:
Blink works on the Arduino Board itself, but if I pull it out and stick it into my breadboard, the program seems to not start. Here are some facts:

happens with or without external crystal 16.000 (Pin 9-10)
happens with or without the 22pF capacitors from crystal to GND (9-GND, 10-GND)
happens with Fuses set to internal OSC or to external clock (Uno default)
happens with or without the ADC VCC (Pin 20) and REFERENCE (Pin 21) Pins @ 5V
happens on 5V and on 3V3
happens with or without external Pullup on RESET Pin (1)
Most of the output Pins sit at 0.8 V


user4361: I found the solution by accident.
While I used my multimeter to measure the voltages between GND and the Pins (for the last fact), I noticed the program running at weird speeds. I. e. the LED started blinking.
What did I measure?
Actually I was just measuring one of the crystal pins (Pin 9 or 10). The sketch went running for a few seconds and very different speeds and then stopped.
This small change in voltage gave the ATMega the clock signal it needs to step through the program.
Maybe I need less capacitance of the two capacitors as mentioned in the comments. I will update the answer with more information later on.
The perfect solution
As pointed out in the comments, I really chose the wrong capacitors. It worked without, but we want the stability so use a bright light and a magnifying glass if you are unsure. Really, do it.

4361: <p>I bought an ATMega328P-PU and burned OptiBoot onto it using a second <em>Arduino Uno R3</em> with great success.</p>

<p>I then put the microcontroller back on the (empty) Uno R3 (DIP) Board for programming, connected USB and uploaded the blink sketch successfully.</p>

<p>Now to the weird stuff:</p>

<p><code>Blink</code> works on the Arduino Board itself, but if I pull it out and stick it into my breadboard, the program seems to not start. Here are some facts:</p>

<ul>
<li>happens with or without external crystal <code>16.000</code> <em>(Pin 9-10)</em></li>
<li>happens with or without the 22pF capacitors from <code>crystal</code> to <code>GND</code> <em>(9-GND, 10-GND)</em></li>
<li>happens with Fuses set to internal OSC or to external clock <em>(Uno default)</em></li>
<li>happens with or without the <code>ADC VCC</code> <em>(Pin 20)</em> and <code>REFERENCE</code> <em>(Pin 21)</em> Pins @ 5V</li>
<li>happens on 5V and on 3V3</li>
<li>happens with or without external Pullup on <code>RESET</code> Pin (1)</li>
<li>Most of the output Pins sit at <code>0.8 V</code></li>
</ul>
 4361: <h2>I found the solution by accident.</h2>

<p>While I used my multimeter to measure the voltages between GND and the Pins (for the last fact), I noticed the program running at weird speeds. I. e. the LED started blinking.</p>

<h2>What did I measure?</h2>

<p>Actually I was just measuring one of the <code>crystal</code> pins <em>(Pin 9 or 10)</em>. The sketch went running for a few seconds and very different speeds and then stopped.</p>

<p>This small change in voltage gave the ATMega the <code>clock</code> signal it needs to step through the program.</p>

<p>Maybe I need less capacitance of the two capacitors as mentioned in the comments. I will update the answer with more information later on.</p>

<h2>The perfect solution</h2>

<p>As pointed out in the comments, I really chose the wrong capacitors. It worked without, but we want the stability so use a bright light and a magnifying glass if you are unsure. Really, do it.</p>
