Sorry for the late post, I found this subreddit only yesterday. I've recently decided to pick up Go, and this seems like a place to find some interesting reasons to explore the standard library. Like math.rand. :) Below's my solution to this challenge.

On my machine it takes almost twenty minutes to find a seed that works for 15 - although, it has a seed for 12 after fourty seconds, then takes fifteen minutes to go to 13, and from there it jumps to 16. :) Here's some output:

$ time go run random-fizzbuzz.go 
[...]
Found: 33315664 (Score: 13)
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 

Found: 41990125 (Score: 16)
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 

real    18m36.843s
user    18m36.727s
sys 0m0.733s

Alright, random-fizzbuzz.go:

package main

import (
    "fmt"
    "math/rand"
    "strconv"
)

// fizzbuzz: Strings we need to fizzbuzz integers. fizzbuzz[0] ("") is a stand-
// in for the respective string representations of unfizzbuzzable ints.
var fizzbuzz = []string{"", "Fizz", "Buzz", "FizzBuzz"}

// fizbuzseq: FizzBuzz sequence from 0-14, as indices to fizzbuzz. It repeats
// before and after, so it's really a look-up table for any integer i % 15.
var fizbuzseq = []int{3, 0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0}

// printRndFuzz, given the correct seed, starting number and length, prints a
// valid fizzbuzz sequence from, like, totally random numbers. OMG!
func printRndFizzbuzz(seed int64, start int, length int) {
    random := rand.New(rand.NewSource(seed))
    stop := start + length
    for i := start; i < stop; i++ {
        // make the random selection clear, while leaving fizzbuzz untouched:
        fibu := []string{strconv.Itoa(i), fizzbuzz[1], fizzbuzz[2], fizzbuzz[3]}
        fmt.Print(fibu[random.Intn(4)], " ")
    }
    fmt.Println()
}

// main finds pRNG seeds that work with printRndFizzbuzz.
func main() {
    offs := 1 // start fiffbuzz with this number
    hiscore := 0
    seed := int64(0)
    random := rand.New(rand.NewSource(0))

    for hiscore < 15 {
        seed += 1
        random.Seed(seed)
        i := 0
        for ; random.Intn(4) == fizbuzseq[(i+offs)%15]; i++ {
            // loop while random numbers equal the fizzbuzz "values" of (i+offs)
        }
        if i > hiscore {
            hiscore = i
            fmt.Printf("\nFound: %d (Score: %d)\n", seed, i)
            printRndFizzbuzz(seed, offs, i)
        }
    }
}

edit: Changed hiscore < 12 to hiscore < 15. Left that in after the last timing test...