Para prefixar uma linha com uma string, use uma substituição ( s ) e substitua ^ , a âncora de início da linha:
$ printf 'line1\nline2\n' | sed '1s/^/PREFIX/'
PREFIXline1
line2
Use a para acrescentar linhas depois de alguma linha e i para inserir uma linha antes de outra linha. Os comandos a e i não servem para modificar linhas, apenas adicionando linhas.
"Esse comportamento pode depender?" Não. Como Stéphane Chazelas aponta nos comentários, "Isso é claramente um bug", e o GNU sed não mostra o comportamento descrito.
Com relação à sua pergunta "Se uma linha não terminar em um caractere de nova linha, ainda é uma linha?", POSIX define uma" linha "como
A sequence of zero or more non-<newline> characters plus a terminating <newline> character.
Então a resposta para essa pergunta é "não, não é uma linha".