My first suggestion is to write a is_valid function since you are using this code in quite a few places:

is_valid <- function(x)
   grepl('^((GIR 0AA)|((([A-PR-UWYZ][A-HK-Y]?[0-9][0-9]?)|(([A-PR-UWYZ][0-9][A-HJKSTUW])|([A-PR-UWYZ][A-HK-Y][0-9][ABEHMNPRV-Y]))) [0-9][ABD-HJLNP-UW-Z]{2}))$', x)

Then, it is also a good idea to write a separate function for each of the fixes you have. It makes your code easier to test and reuse. Also, when using appropriate function names, it makes your code self-explanatory and can replace all the comments:

fix_case <- toupper

fix_space <- function(x)
   sub("^((GIR 0AA)|((([A-PR-UWYZ][A-HK-Y]?[0-9][0-9]?)|(([A-PR-UWYZ][0-9][A-HJKSTUW])|([A-PR-UWYZ][A-HK-Y][0-9][ABEHMNPRV-Y])))))([0-9][ABD-HJLNP-UW-Z]{2})$","\\1 \\9", x)

fix_zero_1 <- function(x)
   sub("([A-Z][0-9]|[A-Z][A-Z]|[A-Z][A-Z][0-9])[O]","\\10", x)

fix_zero_2 <- function(x) {
   x <- sub("^((GIR 0AA)|((([A-PR-UWYZ][A-HK-Y]?[0-9][0-9]?)|(([A-PR-UWYZ][0-9][A-HJKSTUW])|([A-PR-UWYZ][A-HK-Y][0-9][ABEHMNPRV-Y]))))) ([O][ABD-HJLNP-UW-Z]{2})$", "\\1 0\\9", x)
   sub("0O", "0", x)
}

With these, your code can simplify to:

postcodes <- c(
  "GIR 0AA",
  "M2 0AB",
  "M2 OAB",
  "M2 0ab",
  "M1 1AA",
  "M11AA",
  "M60 1NW",
  "M6O 1NW",
  "M601NW",
  "CR2 6XH",
  "CR26XH",
  "DN55 1PT",
  "DN551PT",
  "W1A 1HQ",
  "W1A1HQ",
  "w1a 1hq",
  "EC1A 1BB",
  "EC1A1BB"
)

bg <- postcodes
bg <- ifelse(is_valid(bg), bg, fix_case(bg))
bg <- ifelse(is_valid(bg), bg, fix_space(bg))
bg <- ifelse(is_valid(bg), bg, fix_zero_1(bg))
bg <- ifelse(is_valid(bg), bg, fix_zero_2(bg))

data.frame(original   = postcodes,
           best_guess = bg,
           is_valid   = is_valid(bg))

Note how I am using vectors everywhere and only in the end putting the results in a data.frame. Indeed, there is arguably no need for a data.frame until you want to see the results in a nice format, at the very end. Keeping things in vectors avoid the repetitive pc$ and the annoying conversion from character vectors to factors (what forced you to use as.character).

I have slightly modified your algorithm, where instead of replacing valid postcodes by "" so they won't get affected by fixes, I am propagating a vector of valid or "best guess" codes (bg) via the construct:

bg <- ifelse(is_valid(bg), bg, som_fix(bg))

This removes the need for the error-prone paste() step at the end of your code.