The problem is because you are specifing a max ylim
of -45, and the data are being cut accurately at that latitude. Clearly the actual bounds of the plot are calculated in a separate way, which is probably to do with some kind of conservative assumption based on the resulting projected limits (but that I know nothing about without exploring the source code).
You can avoid the problem by setting up a dummy plot that doesn't draw the coastline, then add the data on top with an increased ylim
:
library(maps)
library(mapproj)
ylim = c(-90,-45)
orientation=c(-90, 0, 0)
x11()
par(mar=c(1,1,1,1))
m <- map("world", plot=FALSE)
map("world",project="stereographic", orientation=orientation, ylim=ylim, col = "transparent")
map("world",project="stereographic", orientation=orientation, ylim=ylim + c(-5, 5), add = TRUE)
map.grid(m, nx=18,ny=18, col=8)
box()
BTW, this strategy won't work for all projections since some will imply overlap for some data limits, but Polar Stereographic just extends out from the centre so there's no such problem here.
Also, there would be a more up to date way to do this with maptools, rgdal and rgeos that would allow you to use data sharing a proper PROJ.4 Stereographic projection (but I haven't quite figured out the clipping step). The projections in mapproj are "shape-only" and it would be a bit of work to get other data into those, afaik.