3 Listed run times
source | link

Finds the line count of "First Pattern", then uses head to display lines above it, pipes through tac and greps it.

head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2" 

Eg.

head --lines=+6 file | tac | grep -m1 "Pattern2" 

This is more reliable then using -m 1000000 in grep. Since speed is important to OP, I checked the run time and it also appears to be faster then all other current answers (on my system)

wc -l file
25910209 file

time awk '/Pattern2/ {line=$0; next}; /First Pattern/ {print line; exit}' file
Pattern2:TheRightBar

real  0m2.881s
user  0m2.844s
sys 0m0.036s

time sed '/Pattern2/h;/First Pattern/!d;x;/Pattern2/!d;q' file
Pattern2:TheRightBar

real  0m5.218s
user  0m5.192s
sys 0m0.024s

time (grep -m1 "First Pattern" file -B 10000000 | tac | grep -m1 "Pattern2")

real  0m0.624s
user  0m0.552s
sys 0m0.124s

time (head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2")
Pattern2:TheRightBar

real  0m0.586s
user  0m0.528s
sys 0m0.160s

Finds the line count of "First Pattern", then uses head to display lines above it, pipes through tac and greps it.

head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2" 

Eg.

head --lines=+6 file | tac | grep -m1 "Pattern2" 

Finds the line count of "First Pattern", then uses head to display lines above it, pipes through tac and greps it.

head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2" 

Eg.

head --lines=+6 file | tac | grep -m1 "Pattern2" 

This is more reliable then using -m 1000000 in grep. Since speed is important to OP, I checked the run time and it also appears to be faster then all other current answers (on my system)

wc -l file
25910209 file

time awk '/Pattern2/ {line=$0; next}; /First Pattern/ {print line; exit}' file
Pattern2:TheRightBar

real  0m2.881s
user  0m2.844s
sys 0m0.036s

time sed '/Pattern2/h;/First Pattern/!d;x;/Pattern2/!d;q' file
Pattern2:TheRightBar

real  0m5.218s
user  0m5.192s
sys 0m0.024s

time (grep -m1 "First Pattern" file -B 10000000 | tac | grep -m1 "Pattern2")

real  0m0.624s
user  0m0.552s
sys 0m0.124s

time (head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2")
Pattern2:TheRightBar

real  0m0.586s
user  0m0.528s
sys 0m0.160s
2 Improved answer
source | link

Should it only have outputFinds the line count of Pattern2:TheRightBar?"First Pattern", then uses head to display lines above it, pipes through tac and greps it.

tachead --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m2m1 'Pattern'"Pattern2" 

Eg.

head --lines=+6 file | tailtac | grep -n1m1 "Pattern2" 

Should it only have output of Pattern2:TheRightBar?

tac file | grep -m2 'Pattern' | tail -n1

Finds the line count of "First Pattern", then uses head to display lines above it, pipes through tac and greps it.

head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2" 

Eg.

head --lines=+6 file | tac | grep -m1 "Pattern2" 
    Post Undeleted by Miati
    Post Deleted by Miati
1
source | link

Should it only have output of Pattern2:TheRightBar?

tac file | grep -m2 'Pattern' | tail -n1