Here is the email I received in my Yahoo! account:

Dear Paypal User

You have added o0_yuna_baby_o0@yahoo.com as a new email address for
your PayPal account.

If you did not authorize this change or if you need assistance with
your account, please contact PayPal customer service at:

http://www.paypalonlineupdate.info/i...cmd=_login-run

Thank you for using PayPal!
The PayPal Team

Please do not reply to this e-mail. Mail sent to this address cannot be
answered. For assistance, log in to your PayPal account and choose the
"Help" link in the header of any page.

And the Header:

X-Apparently-To: XXXXXXXXXX@yahoo.com via 68.142.201.224; Mon, 04 Jul 2005 08:02:42 -0700
X-YahooFilteredBulk: 62.212.83.161
X-Originating-IP: [62.212.83.161]
Return-Path: <sietse@sietse.nu>
Authentication-Results: mta198.mail.dcn.yahoo.com from=paypal.com; domainkeys=neutral (no sig)
Received: from 62.212.83.161 (EHLO karin.wiseadvise.net) (62.212.83.161) by mta198.mail.dcn.yahoo.com with SMTP; Mon, 04 Jul 2005 08:02:42 -0700
Received: from apache by karin.wiseadvise.net with local (Exim 4.42) id 1DpSSN-0006b7-TA for jameschwab@yahoo.com; Mon, 04 Jul 2005 17:01:59 +0200
To: XXXXXXXXXX@yahoo.com
Subject: Unauthorized Access: (Routing Code: 301-Y712-P390)
From: service@paypal.com Add to Address BookAdd to Address Book
Reply-to:
MIME-Version: 1.0
Content-Type: text/plain
Content-Transfer-Encoding: 8bit
Message-Id: <E1DpSSN-0006b7-TA@karin.wiseadvise.net>
Date: Mon, 04 Jul 2005 17:01:59 +0200
X-WiseAdvise-MailScanner-Information: Please contact the ISP for more information
X-WiseAdvise-MailScanner: Found to be clean
X-MailScanner-From: sietse@sietse.nu
Content-Length: 530

The Originating IP of 62.212.83.161 resolves to the following (per Sam Spade):

Trying 62.212.83.161 at ARIN
Trying 62.212.83 at ARIN

OrgName: RIPE Network Coordination Centre
OrgID: RIPE
Address: P.O. Box 10096
City: Amsterdam
StateProv:
PostalCode: 1001EB
Country: NL

ReferralServer: whois://whois.ripe.net:43

NetRange: 62.0.0.0 - 62.255.255.255
CIDR: 62.0.0.0/8
NetName: RIPE-C3
NetHandle: NET-62-0-0-0-1
Parent:
NetType: Allocated to RIPE NCC
NameServer: NS-PRI.RIPE.NET
NameServer: SEC1.APNIC.NET
NameServer: SEC3.APNIC.NET
NameServer: NS2.NIC.FR
NameServer: SUNIC.SUNET.SE
NameServer: AUTH03.NS.UU.NET
NameServer: TINNIE.ARIN.NET
Comment: These addresses have been further assigned to users in
Comment: the RIPE NCC region. Contact information can be found in
Comment: the RIPE database at http://www.ripe.net/whois
RegDate: 1997-04-25
Updated: 2004-03-16

(Continued)

www.paypalonlineupdate.info whois information:

Domain Name: PAYPALONLINEUPDATE.INFO
Created On: 03-Jul-2005 17:38:27 UTC
Last Updated On: 04-Jul-2005 14:43:04 UTC
Expiration Date: 03-Jul-2008 17:38:27 UTC
Sponsoring Registrar: YesNIC Co., Ltd. (R158-LRMS)
Status: ACTIVE
Status: OK
Registrant ID: C10500853-LRMS
Registrant Name: Peter Jaly
Registrant Organization: Hosting
Registrant Street1: 7 Viewland Drive
Registrant City: 7 Viewland Drive
Registrant Postal Code: 4562
Registrant Country: AU
Registrant Phone: +82.78676787868
Registrant Email: woolleyc1949@yahoo.com
Admin ID: C10500856-LRMS
Admin Name: Peter Jaly
Admin Organization: Hosting
Admin Street1: 7 Viewland Drive
Admin City: 7 Viewland Drive
Admin Postal Code: 4562
Admin Country: AU
Admin Phone: +82.78676787868
Admin Email: woolleyc1949@yahoo.com
Billing ID: C10500857-LRMS
Billing Name: Peter Jaly
Billing Organization: Hosting
Billing Street1: 7 Viewland Drive
Billing City: 7 Viewland Drive
Billing Postal Code: 4562
Billing Country: KR
Billing Phone: +82.78676787868
Billing Email: woolleyc1949@yahoo.com
Tech ID: C10500857-LRMS
Tech Name: Peter Jaly
Tech Organization: Hosting
Tech Street1: 7 Viewland Drive
Tech City: 7 Viewland Drive
Tech Postal Code: 4562
Tech Country: KR
Tech Phone: +82.78676787868
Tech Email: woolleyc1949@yahoo.com
Name Server: NS1.PAYPALONLINEUPDATE.INFO
Name Server: NS2.PAYPALONLINEUPDATE.INFO
Clearly not a Paypal site...
Anyone seen this before?