Learn Russian: Если бы не упорство команды, мы бы провалили план. - If it weren't for the team's perseverance, we would have failed the plan.

Normally, yes, negation can trigger the Genitive. However, the structure если бы не (meaning "if it weren't for") is a special fixed construction that always takes the Nominative case. You can think of it as literally meaning "If [the team's perseverance] did not exist."

How do we know this means "would have failed" (past) rather than "would fail" (present)?

Russian conditionals don't have separate forms for the present and the past. The combination of a past tense verb (провалили) plus бы covers both "would fail" and "would have failed". You have to rely entirely on the context to know that this refers to a past event.

Could the бы in the second clause go after the verb instead, like мы провалили бы?

Yes, you could absolutely say мы провалили бы план. The particle бы is quite flexible. It usually follows the subject or the verb, often attaching to whatever word the speaker wants to emphasize. Placing it right after the pronoun subject (мы бы) is just very natural conversational flow.

Can I use the verb провалили for failing a test, or is it only for things like plans and missions?

You can use it for tests too! Провалить literally means "to let fall through" or "to collapse" (from the root валить, to topple/throw down). It is the standard verb for failing an exam (провалить экзамен) as well as failing an assignment, interview, or plan.