Other parts of the PIC (timers etc - sorry - that's wrong!) use Tosc and can take advantage of the full 40MHz, it's just the instruction cycle which needs four oscillator cycles to complete one instruction (sometimes it needs double that for some instructions).
If you need much faster than that (and faster than my 44MHz overclock) then you need a different PIC. The 18F4550 and similar parts with USB have a 48MHz standard maximum (might be overclockable) and the PLL has x2,3,4 and 6 modes for more flexible crystal choice.
The dsPIC30F4013 and similar can go up to 120MHz internally, with up to x16 PLL, giving you 30 MIPS - three times the 18F4620's official maximum.
---------- Post added at 00:31 ---------- Previous post was at 00:27 ----------
As far as the PIC is concerned, there is no difference between a metal can oscillator and a crystal+capacitors. A 10MHz oscillator, or a 10MHz crystal will both give the PIC 10MHz, which it can them multiply with its PLL. The oscillator simply gives a ready-to-use digital clock, whereas the crystal needs an oscillator circuit to give the clock (which is inside the PIC - that's why you need two pins to connect a crystal). The oscillator connects with a single connection to the OSC1 pin; the OSC2 pin is not needed and can be configured as an I/O if you want.