Well, watching most anime basically requires four things. A player capable of handling the matroska container (no problem AFAIK), AAC audio (IIRC, again not a problem), 720p h264 video (might be an issue), and ASS subtitles (might be an issue). The last two tend to be the biggest problems on desktop linux. The video acceleration API seems to be defecient or something... Intel's working to create a new VA-API standard. Anime encoders also aren't all on the same page with h264 L4.1 or L5.1. The former is what BluRay uses, and is generally acceleratable with hardware. The latter generally isn't except with the latest iterations of ATI and nVidia cards. Without HW acceleration I wouldn't expect the Pandora's CPU to be even close to fast enough for 720p. The subtitles basically work in very recent builds of VLC (and not perfectly) and MPlayer. Even then, animated subtitles can be a beast, using ~10% of a Core2 Duo. IMO, as things currently stand, I'd expect something between jittering to slideshow during OPs when the CPU is taxed with both fast motion video and advance subtitles. Hard subbed Xvid files should play fairly easily, but I'd suspect one would have difficulty reading the subtitles, since text doesn't resize all that well (one of the disadvantages of hard subs).
Hopefully these issues will improve over time. Reencoding is an option, technically. I think it's cheating myself, since one could easily reencode a video to play on basically anything with a screen (e.g. 8x8 dot matrix watch screen). Plus, the Pandora is perfectly capable of downloading video via BitTorrent or Samba, or whatever else. I don't want to imagine how long it'd take to reencode high bitrate h264 video using the Pandora itself.