I don't know about any specific micros with bluetooth onboard....not off the top of my head at least, I'm sure they are out there.
CSR makes Bluetooth chips based on their BlueCore technology and they have onboard micros generally. I would maybe look to a chip manufacturer that has a CSR based solution. CSR's website has partner companies listed that use there technology.
One easy solution is the LMX9838 by National, it is an all in one module (including antenna). It includes a complete BT stack up to SPP profile. All you do is inteface via the UART on a micro and communicate to the LMX9838 via AT commands.
So, do you know any good website that has something like a search engine so that I can enter my needings in a microcontroller and it guides me to the correct ones?
Sorry, I do not know of any single website where you can enter or search for the microcontroller to fit your needs.
All I can suggest to do is to go to each of the individual websites for the micro manufacturers...like Freescale, NXP, NEC, Cypress, Microchip, TI, ST, etc. and there will be a search feature on those sites.