In reading through Eve Maler's slides from this year's XML Summer School, she describes the standard IdP discovery problem for an RP initiated authentication event. One of the standard options is "Client tells RP". Putting this together with the proposal by Laurent Michel on the OpenID lists regarding mobile use of OpenIDs, why not just use the convention of an HTTP header to describe the user's IdP? (I suspect this has been proposed before. Feel free to add a comment stating so). This HTTP header would not have to be sent with every request, because the identity agent could detect when an RP needed it from some additional simple HTML markup.
The RP could then do a XRDS (XRI resolution v2.0 section 6) based discovery on the presented URI from the HTTP header. This would allow the IdP to expose multiple services and protocols via a simple XRDS file. The RP would then just pick the the appropriate protocol and endpoint from the XRDS file and start the RP initiated authentication process.
One danger with this kind of a "push" mechanism is that over an untrusted channel the user is susceptible to MIT attacks. With a smart client and SSL I believe this is better than the cookie mechanism. For OpenID it's probably better to take the seatbelt and sxipper approach of just posting the user's OpenID to the OpenID login form. However, for a protocol like SAML2, identifying the IdP in this kind of a manner should improve the user experience.