Winamp sometimes truncates the paths, so you'll get stuff like:
/albums/some other album/song1.mp3
But it sometimes employs some other path truncation method that we've not quite figured out. We never really saw the point of deciphering how they do what they do with playlists, and writing code to compensate for it and all other possible types of playlists, so we just use absolute paths for every playlist entry. In retrospect we probably shouldn't have used .m3u as the M/E playlist file extension, but not all of the developers agreed on this point and so I was 'voted off the island'.
The workaround is to build your playlists in M/E. Sorry if that's not the answer you were looking for.