While not exactly what you're looking for, I have used power-management ICs to accomplish this. For instance, the TPS2113APW. I prefer this specific chip because it allows me to make dual-powered devices that can operate with either a wall-wart or off the USB, automatically preferring wall-power if it is available.
If you don't need dual-powered, you could use something like the MIC2545A
Ultimately, any capacitance "behind" the power-management IC (i.e. hooked up to the IC outputs) isn't "seen" by the USB; the bus only sees the capacitance "in front of" the IC (i.e. hooked up to IC inputs).
You still have to worry about inrush current - the "plus any capacitive effects visible through the regulator" part of the spec - but those ICs also have variable current limiting. Figure out the parallel resistances that you need to have 100 mA limitation and 500 mA limitation (and optionally n mA limitation if you want to limit wall-power), and then use FETs to short out the resistors as needed to enable various limitations.
Through these chips, I have attached PCBs with several hundreds of uF to the USB, and a DMM set to fast current max verified that the inrush during attachment did not exceed 100 mA.
The generic answer to this question is yes, the VBUS (+5V from cable) must be connected to the device even if it is self-powered. The reason is as follows:
To start the connect process on host side, the device must pull up D+ (in case of FS/HS mode), or D- (in case of LS device).
However, USB specifications have a mandatory requirement that no USB device should source any current on any interface pin unless it is connected to a cable, see section 7.1.5.1, which reads,
The voltage source on the pull-up resistor must be derived from or
controlled by the power supplied on the USB cable such that when VBUS
is removed, the pull-up resistor does not supply current on the data
line to which it is attached.
If a USB device doesn't have this control, one of data lines will be a source of current. Premature assertion of pull-ups were a source of problems for some legacy USB hosts. That's why this rule was instituted, and there is a special test for this in USB-IF certification program.
Therefore, the USB VBUS is an important "side-band" signal in USB connect protocol. As such, normal USB device ICs do have a separate input pin to sense the presence of USB host. Some IC manufacturers (e.g. FT232H, MCP2221, etc.) skip on this requirement, assuming that their chip will be solely used in bus-powered configuration, where the pull-up control requirement is automatically satisfied. However, when designing these chips into self-powered designs, some extra circuit efforts are needed to link the enabling of pull-ups with presence of VBUS on the USB port.
Regarding the USB connect "handshake" protocol, USB doesn't rely on current drawn from VBUS. The protocol is this: Host port must have VBUS active; VBUS is connected to device; device sees the VBUS and pulls-up 1.5k on one of D+/D- wires; host sees this connect, and after a 100ms delay asserts USB_RESET signaling (SE0 etc.).
Best Answer
If it is capable of being bus-powered, then I would report it as such. The end result of the power negotiation is a maximum that you're not allowed to exceed, but you don't actually have to use it. (The maximum power is rarely enforced, but every once in a while it is.)
To make your device a bit smarter, and if you don't mind some extra work, you might want to have two configurations, as Simon mentioned. The tricky part would be to determine what to do if you're in self-power mode and you lose the external power. You're not allowed more than 2mA from the bus without dropping off the bus and re-enumerating (which may not succeed in giving you more power), and you just lost your supply to do your intended function. So now what?