If you can use awk, then this makes it:
$ awk '/tata/ && !f{f=1; next} 1' file
titi
toto
tata
To save your result in the current file, do
awk '...' file > tmp_file && mv tmp_file file
Explanation
Let's activate a flag whenever tata is matched for the first time and skip the line. From that moment, keep not-skipping these lines.
/tata/ matches lines that contain the string tata.
{f=1; next} sets flag f as 1 and then skips the line.
!f{} if the flag f is set, skip this block.
1, as a True value, performs the default awk action: {print $0}.
Another approach, by Tom Fenech
awk '!/tata/ || f++' file
|| stands for OR, so this condition is true, and hence prints the line, whenever any of these happens:
tata is not found in the line.
f++ is true. This is the tricky part: first time f is 0 as default, so first f++ will return False and not print the line. From that moment, it will increment from an integer value and will be True.