This sounds allot like a safelight problem, but IDK. Run a safelight check on your set up. It's a good idea to do this every so often, especially when you bring a new paper in to the darkroom. Safelight problems are the cause of more crappy printing than all other things combined. There are allot of threads in the archives that will tell you how to do this. Use the method that involves preflashing your paper. One paper may have a problem with your safelight, another may not, so just because one kind of paper has no problem, doesn't mean anything.
No safelight problem? Take a sheet of the offending paper, and process it directly, in the dark, without exposing it, if the artifact is still there, it is the paper. If it isn't there, give another sheet a bit of a flash, just enough to get it started grey (no image) and process that (because some things need a baseline exposure to show up), and so on, until you eliminate enough variables that you know what is going on, otherwise, you are just milking the guppy.