I got a new phone today, a Samsung A737 from ATT. I signed up for their media net unlimited for an additional $15 and it gives me internet access, not only on my phone, but on my N800 too.
I have the Vagalume Last.FM client installed on my N800, and guess what? The 3G connection is sufficient for streaming! :)
I tested it out today, only a 5 mile trip on I-15 (SLC metro area). At 75 MPH, I went through about 3 songs. I advanced (skipped) the song about 5 times, and each time it went to the next song very rapidly (1-2 seconds delay). The whole time the music only cut out once when I first got onto the freeway, but only for about 2 seconds and it corrected itself.
I am extremely giddy at all the geeky prospects that lie ahead for me :)