Many microcontrollers are fully static, i.e. that the clock can be completely stopped, or that you can run it at frequencies like 0.1 Hz, for instance, for 1 instruction per 10 seconds (might be useful for debugging). Some components on the die may require a minimum clock frequency to work, however, like an ADC: the sampling capacitor will discharge if you don't complete a conversion within a certain time.
That being said, the controller's clock will cause EMI over a band much wider than just the clock's frequency. The shorter the rise/fall of a digital signal the more energy there will be in the harmonics. To decrease EMI some microcontrollers, like Freescale's MC9S08, have (switchable) slew-rate controlled I/Os.
I'm no lawyer, but have been thru the FCC testing process a few times. For a ordinary device that doesn't deliberately transmit (called "unintentional radiator" by the FCC), there is no legal requirement for certifcation. There are legal requirements for what it is allowed to emit, but it up to you how to make sure your device works within the rules.
You can simply sell a unintentionally radiating device without testing. However, if someone files a complaint and the device is found to exceed the legal radiation limits, you're in deep doodoo. If you had the device tested by a accredited test lab and they determined it was within the limits, your legal case will be much better. The FCC still has the right to force you to withdraw the product and even confiscate every unit out there, but if you can show you followed accepted practices of testing then there will be much less of a issue of punative actions.
Intentional radiators are a different story. You do have to have FCC certification to legally sell one in the United States. When the device is certified, you get a certification ID, and that ID generally has to be indicated somewhere on the outside of the device where others can see it.
In the case of a bluetooth module, most likely the module vendor has gotten the certification for the module. If not, I wouldn't go near it. Even if so though, you are still on the hook for the product as a whole. The module will also be certified with some restrictions, like a specific list of antennas that it is certified with. If you attach a different antenna, for example, the module is no longer certified and you're on your own.
If you're trying to sell a intentionally radiating product, you'd better talk to a expert early in the process. You can wing it a bit with unitnentional radiators, but you really don't want to play games with intentional radiators, even if you're using a certified module that does all the intentional radiating.
It might be a good idea to talk to a testing house. They generally will know all the rules. Just keep in mind they sell testing services, and their answers may a bit biased towards you needing a lot of testing.
Best Answer
That depends on how you look at it. Every product that is considered an end-user product must have a CE certification. I don't know how the FCC works, but in the case of CE it's self-certification. That means you may just state that your product is CE compliant and that's it. Of course you are always responsible for your product (even if a third party has verified EMC compliance and such). If it ends up interfering with other appliances of injuring someone, your in trouble.
That said... CE is not requires for "component or modules" that are used to manufacture end-products - which one might argue an arduio is. Or is it? Maybe it's a consumer product designed for education and developing. Not sure myself.
I personally think it's still a niche product that is not a standalone device. But I'm no lawyer ;)