Let us consider the following simple topology, where for the sake of simplicity we assume that each Autonomous System (AS) consists of a single BGP router:
Now, let us say that AS3 has received two BGP UPDATEs (one from AS1 and one from AS2), each containing an advertisement for the same prefix P.
AS3 stores the routes that it has received in a database that is called the Adj-RIB-In (the Input Routing Information Base for each Adjacency). Thus, AS3 will have the route for prefix P in two Adj-RIB-In tables: the one for AS1 and the one for AS2.
AS3 first applies inbound policy: it may filter out some of the received advertisements, or it may modify some of the attributes of the received advertisements.
As a matter of implementation (the RFC doesn't talk about implementation) both the pre-inbound-policy and post-inbound-policy are often stored in the Adj-RIB-In. This allows an operator to use CLI show commands to see the route both pre-inbound-policy and post-inbound-policy. It also allows the operator to change the inbound policy without having to ask the neighbor to resend all the routes (this is called a soft refresh).
If the inbound policy rejects the route for prefix P that was received from some neighbor, then it will not be in the Adj-RIB-In (or at least not in the post-policy Adj-RIB-In). Hence it will not be a candidate for becoming the best route (described below), it will not be installed in the forwarding path (also described below), and it will not be advertised to upstream neighbors (you guessed it, also described below).
Every time there is a change in the route for prefix P in any of the Adj-RIB-Ins, BGP runs the "decision process" (choosing the best route) for that prefix P. In this example, AS3 selects a best route (or possibly a set of equally good best routes if multi path is enabled). The rules for selecting the best route are described in RFC4271, and includes rules such as "prefer the route with the shortest AS path".
The selected best route is stored in a database called the Loc-RIB (the Local Routing Information Base). The best route for each prefix (called the active route in many implementations) is stored in the forwarding path (called the FIB for Forwarding Information Base) of the router. Thus, this is the only route that is actually used for forwarding traffic.
When is a route removed from the FIB? Consider the following scenario. At some point in time (T1), the best route was P and this route was installed in the forwarding path. Some time later (T2), routers AS1 and AS2 send UPDATEs and all of the new routes are rejected by inbound policy. It's very simple. At T1 there was a best route in the Loc-RIB. At time T2 that changes: there is no longer a best route in the Loc-RIB. This means that the route has to be removed from the forwarding path (FIB). The route will also be removed from each Adj-RIB-Out which is what we will describe next.
Once the best route has been selected and and installed in the forwarding path, the next steps will advertise the route to upstream routers. (Just think of the traffic flow as a river - thus any router that we SEND and routing update to is a router that we will RECEIVE traffic from).
Just as there is an Adj-RIB-In for each neighbor (with the received routes), there is also an Adj-RIB-Out for each neighbor (with the routes that have been or will be advertised to that neighbor).
As a matter of implementation, multiple neighbors may share a single Adj-RIB-In to save memory. This only works if we know for sure that the same routes will be sent to a group of neighbors (this is one of the reasons many implementations have the concept of a peer-group).
For every route in the Loc-RIB, BGP speaker AS3 will apply some rules specified in the RFC (e.g. prepend its own AS number the the AS-path) and some rules configured by the operator (the outbound policy, e.g. change the MED) and place the modified route in the Adj-RIB-Out for each neighbor.
Note that the outbound policy may also filter routes. In that case, the Loc-RIB has a best route for prefix P, but the Adj-RIB-Out does not have a route for the same prefix P.
Finally, AS3 will advertise the best routes in the Adj-RIB-Out to the BGP neighbor that is associated with that Adj-RIB-Out.
So, to get back to your question #1: when will AS3 send a withdraw to AS4?
AS3 has an Adj-RIB-Out table for neighbor AS4.
Every time the route for P in that Adj-RIB-Out table changes, AS3 sends an UPDATE to AS4.
If the change was: the route used to be P and that route changes to P', then AS3 sends an UPDATE with an advertisement for P'
If the change was: the best route used to be P and that route is removed from the Adj-RIB-Out, then AS3 sends an UPDATE with a withdraw for P.
This is the main rule, but there are a few subtleties about what to send to the BGP neighbor from whom the route was originally received.
Let's say, in this same example, that AS3 selected the route received from AS1 as the best route. What should AS3 send back to AS1?
In this example, we have assumed that all the BGP speakers are in different ASs, i.e. that all BGP sessions are EBGP sessions. In that case, AS3 doesn't have to do anything special: it can send the best route that it received from AS3 back to AS3. This won't cause a routing loop, because AS1 will see it's own AS number in the AS-path and ignore the UPDATE because it realizes it is a loop.
For IBGP sessions (which are not in this example), the situation is a bit more complex. It is not allowed for a BGP speaker to send a route back to the BGP speaker from whom it received the route. Thus, a BGP speaker may have to send a withdraw (a "poison reverse") instead of sending a route back to the BGP speaker from whom it received the route.