It seems to me like this would benefit from a web service that coordinates the assimilation and distribution of BSSIDs rather than randomly generating them and hoping for the best. Providing a mechanism for metrics to be reported would be even better, as it could take into account factors to try and limit the number of times you receive a StreetPass from the same 3DS.
A fair distribution of user-supplied (i.e. personal) MACs could also be done for those who can't change their BSSID for whatever reason. And it could modify the distribution based on volume of StreetPasses received per BSSID to try and keep it balanced.
If I wrote a service that did this and provided an API, does this sound like something anyone's interested in using? I'd also probably make a 'reference' implementation as a Linux daemon.
I also want to eventually address the (lack of) security that this introduces; I've profiled various connections from the 3DS (including SPR, Nintendo Zone, and online features from a few games) and there is a very predictable pattern of connections (and certificates, for most of them) that could be used to construct a fingerprint allowing for slightly better control over MAC filtering.
It'd also be cool to make this whole thing easier, as I'm guessing most of you guys don't really care about hacking around in conf files and setting up NAT chains. All of the involved components (on the Linux side, at least) have an interface for programatically controlling their respective services and querying info from them, so this is definitely possible. I also thought about making an image for the RPi that would come ready-to-go, but I wasn't sure how big of a userbase there was for that.
I'm pretty busy right now with other stuff, but I'll see if I can get something together in a GitHub repo this week sometime.
Are you talking about a custom Streetpass Program or something of that sort?