By default, the paste commands use the [`"` (“unnamed”) register][unnamed]. Effectively, any command that writes to a register also writes to the unnamed register, so yanks, deletes, and changes all affect it. This is why your yank-delete-paste sequence pastes the deleted text instead of the yanked text.

[unnamed]: http://vimhelp.appspot.com/change.txt.html#quotequote

The [`0` register][0] can help here. Any yank commands that do not specify a register put the yanked text in register `0` (in addition to `"`). It is not affected by delete or change operations, so you can use it to paste a yanked line multiple times even if you do intermediate deletes or changes.

[0]: http://vimhelp.appspot.com/change.txt.html#quote0

1. `yy`: Registers `0` and `"` both now have the yanked line.
1. Move to a line to replace.
1. `dd`: Register `"` now has the deleted line, but register `0` still has the yanked line. 
 `"0P`: Paste the originally yanked line from register `0`.
1. Move to the next line to replace.
1. `dd"0P` (same as above)

(Due to the way cursor positioning works when replacing the last line of a buffer, you will want to use `"0p` instead of `"0P`.)

This is very close to [Bruce Ediger’s answer][Bruce Ediger], except that you do not have to specify a register when initially yanking. Using one or more named registers can be very handy though if you need to (for example) replace some lines with `AAA`, but other lines with `BBB` (put `AAA` in register `a`, and `BBB` in register `b` (or leave one of them in register `0`), then paste them accordingly).

[Bruce Ediger]: http://unix.stackexchange.com/a/26659/1107

You can also paste from `0` in line-wise visual mode (`V`) to save a keystroke: `V"0p`.

If you do not like having to type `"0`, you might find a mapping more convenient:

 noremap <Leader>p "0p
 noremap <Leader>P "0P
 vnoremap <Leader>p "0p

---

An alternate approach is to delete to the [`_` (“backhole”) register][blackhole]. When you delete to it, the `"` register is not affected, so your yank-delete-paste sequence can still paste the yanked text from the unnamed register.

1. `yy`: Register `0` and `"` both now have the yanked line.
2. `"_dd`: No change to the registers. 
 `P`: Paste the originally yanked text from register `"`.

[blackhole]: http://vimhelp.appspot.com/change.txt.html#quote_

Again, you might find a mapping more convenient:

 noremap <Leader>d "_d