I've recently discovered this forum, and have been reading this board for the last while ... now I've decided to join the fray.
On flights to Halifax from Toronto, I've seen Rick Mercer and Heather Rankin. I saw Greg Thomey waiting to pick someone up at the airport in St. John's. David Suzuki was a few seats away from me on a recent flight to Vancouver. I've spotted the odd politico here and there in Ottawa. In Calgary, I once saw Rex Murphy in the MLL. A few months ago, I was hanging out in the lounge in Vancouver when in came Brian Mulroney. Just this past weekend, Ralph Klein was at the check-in counter next to mine in Kelowna (he was checking in boxes of local produce--which may be a violation of inter-provincial trade agreements ... I don't know ... I would have done the same if I were going straight home!).
I too have had the pleasure of sitting next to Anne Murray, this time on a flight to Moncton. I was reading my book on the plane, "The City of Yes" by Peter Oliva, in which a Canadian fellow goes to Japan to teach English. In one passage, one Japanese character asks the protagonist, since he's Canadian, if he knows who "Amari" is. The teacher doesn't understand. His friend adds "she's famous, she's a singer", and the teacher's mind clicks in--"Anne Murray!". I could not believe the coincidence. I turned to my seatmate and politely asked "Did you know you were in this book?", showing her the passage I'd just read. She was not aware of this reference and was pleasantly surprised. She graciously autographed the page in which her name is mentioned.
And several years ago, I was fortunate to be seated next to Brian Williams on a flight home from Boston (when the Jays were there). We both grew up in Hamilton, and I knew he attended my high school, but we also (as it turned out) lived on the same street, attended the same church, and became big Formula One fans--another very memorable encounter.
I know these aren't quite like an invitation into Madonna's bed, but it's all I've got.